带表头的单链表的基本操作

#include <stdio.h>
#include <stdlib.h>

#define ERROR 0
#define OK 1
#define Overflow 2
#define Underflow 3
#define Notpresent 4
#define Duplicate 5

typedef int ElemType;
typedef int Status;

typedef struct Node
{
	ElemType elem;
	struct Node *link;
}Node;

typedef struct 
{
	struct Node* head;
	int n;
}Headlist;

Status Init(Headlist *L){
	L->head = (Node*)malloc(sizeof(Node));
	if(!L->head) return ERROR;
	L->head->link = NULL;
	L->n = 0;
	return OK;
}

void Sort(Headlist *L){
	Node *p=L->head,*pre=NULL;
	Node *r=p->link;
	p->link = NULL;
	p=r;				//r保存原来的结点顺序
	while(p != NULL){	
		r = p->link;	//r继续取下一个结点
		pre = L->head;	//pre重新构造L,从头开始循环
		while(pre->link != NULL && pre->link->elem < p->elem)  
            // 如果链表非空 且 新链表与当前结点数值比较
			pre = pre->link;	
        //如果当前要插入的结点值大于循环中当前已排序结点,则取已排序链表下一个结点继续比较
		p->link = pre->link;    
        //找到p要插入的位置后,插入:若3<pre=5<bigger=7<8,p=6,则 p=>bigger
		pre->link = p;			// pre=>p,插入即可
		p=r;					// p继续取下个结点依次按原来顺序循环遍历原来链表
	}
}

void deleleab(Headlist *L, int a,int b){ 
     Node *q = L->head,*p=L->head->link;  // q为上一个,p为当前的
     while( p )
     	if(p->elem >= a && p->elem <= b)
     {
     	q->link = p->link;		// 1 - 2 - 3  1==>3,1的指针域指向3
     	free(p);				//释放2
     	p = q->link;			// 当前的指针变成3
     }else{
        p = p->link;
        q = p->link;
     }      
}

Status Converse(Headlist *L)
{
	Node *p = NULL,*cur= NULL; 
	Node *q = L->head->link;
    if(L->head && L->head->link){		//如果表不存在或是为空,则return ERROR
	while( q != NULL )			//q按照原来的顺序依次遍历各结点	
	{
		cur = q;				//cur为当前结点
		q = q->link;			//q保存下一个结点
		L->head->link = cur;	//为了不动头结点,所以头结点link始终指向当前要加的结点
		cur->link = p;			//当前的link指向上一个结点
		p = cur;				//保存上一个结点
	}
	}else return ERROR;
	return OK;
}

Status Insert(Headlist *L,int j,ElemType x)
{
	Node *p=NULL,*q=NULL;
	int i;
	if(j<-1 || j> L-> n-1) return ERROR;
	p = L->head;
	for(i=0;i<=j;i++) p=p->link;
	q = (Node *)malloc(sizeof(Node));
	q->elem = x;
	q->link = p->link;
	p->link = q;
	L->n++;
	return OK;
}

Status Output(Headlist L)
{
	Node *p = L.head->link;
	if(!L.n) return ERROR;
	while(p){
		printf("%d ",p->elem );
		p = p->link;
	}
	return OK;
}

Status Destory(Headlist *L){
	Node *p=NULL;
	while(L->head){			//不断删除head所指向的内存,直到head被释放
		p = L->head->link;  
		free(L->head);		
		L->head = p;
	}	
	return OK;		
}

Status Delete(Headlist *L,int j){		//下标j
	Node *p = L->head,*q = L->head;		// q = tmp
	int i;
	if(!L->n) return ERROR;
	if ( j<0 || j>L->n) return ERROR;
	for(i = 0 ;i<=j-1;i++) p = p->link;
		q = p;
		p = p->link;
		q->link = p->link;
		free(p);
	return OK;
}

Status Find(Headlist *L,int j,ElemType *x){
	Node *p= L->head;
	int i;
	if ( j<0 || j>L->n) return ERROR;
	for(i = 0 ;i<=j;i++) p = p->link;
		*x = p->elem;
	return OK;
}

int main()
{
	int x;
	Headlist list;
	Init(&list);
	 	Insert(&list,-1,3);
		Insert(&list,0,2);
		Insert(&list,-1,5);
		Insert(&list,2,7);
		Insert(&list,-1,1);
	printf("the linked list is :"); 
	Output(list);
	printf("\nAfter sorted:");
	Sort(&list);
	Output(list);
	printf("\nAfter Conversed:");
	Converse(&list);
	Output(list);
	
	printf("\nAfter delete index of 0,the list is:");
	Delete(&list,0);
	Output(list);

	Find(&list,2,&x);
	printf("\nthe index of 2:%d\n",x);

	Destory(&list);
	system("pause");
	return 0;
}
//无论是什么都要略过head表头结点,表头结点的elem是任意的.

(一)实验中遇到的主要问题及解决方法

1.题目二，带表头的单链表在插入时出现了点问题，书上给出的方法是错的，且是C++代码。于是在尝试理解他的想法及每步Debug中终于写出了正确的代码。（L->head->link = NULL,其中L->head->data 不填）

2.题目二中带表头节点的单链表中插入时for( j=0;j<=i; j++) 和之前j<i以及删除时for( j=0;j<=i-1; j++) 和之前j<i-1有很大不同,通过debug知道了是为了略过第一个表头节点。

3.逆置过程中,为了不动表头,略过第一个表头结点时出现了点麻烦.并且在第一个元素逆置后指向NULL,第二个结点指向第一个结点时没有想明白,后来才想到了先让P=NULL,然后记录上一个结点就能达到效果了.同时还有个问题是一直没有保存原来链表的顺序,再因为P=NULL导致会访问到非法内存而程序崩溃

（二）实验心得

2.题目二中,带表头单链表和不带表头单链表,在删除和插入时的循环条件不同要注意.及初始化时带表头的L->head->link= NULL; 与 无表头的 L->first = NULL;