//Linklist.h
typedef struct Node{
int data; //数据域
struct Node * next; //指针域
}ListNode , * Linklist; //ListNode 结点类型,Linklist 指向结点的指针类型
/*Linklist h; 定义头指针*/ /*ListNode *p; 定义指向某结点的指针,两者类型相同*/
单链表
1.初始化空表，建立头结点
Linklist initll(){
Linklist h;
h = (Linklist)malloc(sizeof(ListNode));
if(h!=NULL)
h->next = NULL;
else
printf("分配空间失败！\n");
return h;
}-
2.建立单链表
int Inpll(Linklist h,int n){ //形参：头指针，结点个数ListNode *p,*tail; int i; tail = h; for(i=0;i<n;i++) { p=(ListNode * )malloc(sizeof(ListNode)); scanf("%d",&(p->data)); p->next = NULL; tail -> next = p; tail = p; //tail 永远抓住最后一个结点 } return 1; } -
3.往非递减有序的单链表中插入一个结点后，链表仍有序
void Insll(Linklist h,int x){
ListNode p,q,*temp;q =(Linklist)malloc(sizeof(ListNode)); q->data=x; if(h->next==NULL) //原链表为空 { h->next=q; q->next=NULL; return; } for(p=h->next,temp=h;p!=NULL;temp=p,p=p->next) { if(p->data>=x){ q->next = p; //q的指针域指向当前结点 temp->next = q; //前一个结点的指针域指向q break; } else if(p->next==NULL) //x比原链表中所有结点的值都大,需把q放在最后 { p->next=q; q->next=NULL; break; } } } -
4.遍历单链表
int trall(Linklist h){
ListNode * p;if(h->next==NULL) //空表不遍历 return 0; for(p=h->next;p!=NULL;p=p->next){ printf("%d\t",p->data); } printf("\n"); return 1; }
单循环链表
*** 特点：最后一个结点的指针域永远指向头结点 ***
-
1.建立带头结点的单循环链表
int ReInpll(Linklist h,int n){ ListNode *p,*tail; int i; /*h->next=NULL; //不带头结点创建单循环链表 scanf("%d",&(h->data));*/ tail = h; for(i=0;i<n;i++) { p=(ListNode * )malloc(sizeof(ListNode)); scanf("%d",&(p->data)); p->next = NULL; tail -> next = p; tail = p; //tail 永远抓住最后一个结点 } p->next=h; //最后一个结点的指针域指向头指针 return 1; } -
2.删除单循环链表中所有值为x的元素
void DelX_LL( Linklist h, int x){
ListNode p,q;
q=h;for(p=q->next;p!=h;p=q->next){ if(p->data==x){ q->next=p->next; free(p); //回收被删除的结点 continue; //不再执行下面的语句 } q=q->next; } } -
3.遍历单循环链表
int traRell(Linklist h){ListNode * p; if(h->next == h) //空表不遍历 return 0; for(p=h->next;p!=h;p=p->next){ printf("%d\t",p->data); } printf("\n"); return 1; }
单链表和单循环链表的区别
1.** 尾结点的指针域 **
单链表的尾结点的指针域指向NULL；
单循环链表的尾结点的指针域指向头结点。2.** 判断链表为空的条件 **
判断单链表（带头结点）是否为空,是判断头结点的指针域是否为空。
if(head->next==NULL)
判断单循环链表（带头结点）是否为空,是判断头结点的指针域是否指向自身。
if(h->next == head)
- 3.** 循环的条件 **
在算法中，
单链表的循环条件是：
p != NULL; //p结点不为空
或者
> p->next != NULL; //p结点的指针域不为空
单循环链表的循环条件是：
p != head; //p结点不等于头指针
