单链表数据结构C语言

1、单链表的建立（头插法）写一算法用头插法建立无头结点的单链表，结果返回单链表的头指针typedef char DataType;typedef struct nodeDataType data;struct node *next;ListNode;typedef ListNode *LinkList;LinkList CreateListF(void)char ch;LinkList head;ListNode *s;head=NULL;ch=getchar();while(ch!=n)s=(ListNode*)malloc(sizeof(ListNode);s-data=ch;s-next=h

2、ead;head=s;ch=getchar();return(head);单链表的打印写一算法打印不带头结点的单链表head中每个结点的值typedef char DataType;typedef struct nodeDataType data;struct node *next;ListNode;typedef ListNode *LinkList;void PrintList(LinkList head)ListNode *p;for(p=head;p;p=p-next) printf(%c,p-data);printf(n);单链表的建立（尾插法）写一算法用尾插法建立无头结点的单链表，

3、结果返回单链表的头指针typedef char DataType;typedef struct nodeDataType data;struct node *next;ListNode;typedef ListNode *LinkList;LinkList CreateListR(void)char ch;LinkList head;ListNode *s,*r;head=NULL;r=NULL;while (ch=getchar()!=n)s=(ListNode *)malloc(sizeof(ListNode);s-data=ch;if (head=NULL) head=s;else r-

4、next=s;r=s;if (r!=NULL) r-next=NULL;return(head);单链表的建立（尾插法）写一算法用尾插法建立带头结点的单链表，结果返回单链表的头指针typedef char DataType;typedef struct nodeDataType data;struct node *next;ListNode;typedef ListNode *LinkList;LinkList CreateListR1(void)char ch;LinkList head=(ListNode *)malloc(sizeof(ListNode);ListNode *s,*r;r

5、=head;while (ch=getchar()!=n)s=(ListNode *)malloc(sizeof(ListNode);s-data=ch;r-next=s;r=s;r-next=NULL;return(head);单链表的打印写一算法打印带头结点的单链表head中每个结点的值typedef char DataType;typedef struct nodeDataType data;struct node *next;ListNode;typedef ListNode *LinkList;voidPrintList(LinkList head)ListNode *p;for(p

6、=head-next;p;p=p-next) printf(%c,p-data);printf(n);单链表的查找写一算法在带头结点的单链表head中查找第i个结点typedef char DataType;typedef struct nodeDataType data;struct node *next;ListNode;typedef ListNode *LinkList;LinkList GetNode(LinkList head,int i)int j;ListNode *p;p=head;j=0;while (p-next & jnext;j+;if (i=j) return(p)

7、;else return(NULL);单链表的查找写一算法在带头结点的单链表head中查找其值为key的结点typedef char DataType;typedef struct nodeDataType data;struct node *next;ListNode;typedef ListNode *LinkList;LinkList LocateNode(LinkList head,DataType key)ListNode *p=head-next;while (p&p-data!=key) p=p-next;return(p);单链表的插入写一算法将值为x的新结点插入到带头结点的单

8、链表head的第i个结点的位置上typedef char DataType;typedef struct nodeDataType data;struct node *next;ListNode;typedef ListNode *LinkList;void InsertList(LinkList head,DataType x,int i)ListNode *p,*s;p=GetNode(head,i-1);/寻找第i-1个结点if(p=NULL)printf(插入位置非法n);exit(0);s=(ListNode *)malloc(sizeof(ListNode);s-data=x;s-

9、next=p-next;p-next=s;2单链表的删除写一算法删除带头结点的单链表中的第i个结点typedef char DataType;typedef struct nodeDataType data;struct node *next;ListNode;typedef ListNode *LinkList;void DeleteList(LinkList head,int i)ListNode *p,*r;p=GetNode(head,i-1);/寻找第i-1个结点if(p=NULL|p-next=NULL)printf(删除位置非法n);exit(0);r=p-next;p-next

10、=r-next;free(r);2单链表的逆置试用单链表作为存储结构，实现线性表(a0,a1,an-1)就地逆置的操作，所谓“就地”指辅助空间应为O(1)typedef char DataType;typedef struct nodeDataType data;struct node *next;ListNode;typedef ListNode *LinkList;void InverseList(LinkList *head)ListNode *p,*t,*h;h=(*head)-next;p=h-next;h=(*head)-next;h-next=NULL;while(p!=NULL

11、)t=p-next;p-next=h;h=p;p=t;(*head)-next=h;2单链表的长度在带头结点的单链表上实现线性表的ListLength(L)运算typedef char DataType;typedef struct nodeDataType data;struct node *next;ListNode;typedef ListNode *LinkList;int ListLength(LinkList L)int i=0;ListNode *p;for(p=L-next;p;p=p-next) i+;return(i);2单链表的长度在不带头结点的单链表上实现线性表的Lis

12、tLength(L)运算typedef char DataType;typedef struct nodeDataType data;struct node *next;ListNode;typedef ListNode *LinkList;int ListLength(LinkList L)int i=0;ListNode *p;for(p=L;p;p=p-next) i+;return(i);2有序单链表的插入设单链表L是一个递减有序表，试写一算法将x插入其中后仍保持L的有序性（从头结点开始搜寻适当的插入位置，然后插入）typedef char DataType;typedef struc

13、t nodeDataType data;struct node *next;ListNode;typedef ListNode *LinkList;void InsertSortList(LinkList *L, DataType x)LinkNode *p,*s;p=*L;if (p=NULL | x=p-data)s=(ListNode *)malloc(sizeof(ListNode);s-data=x;s-next=p;*L=s;elsewhile (p-next!=NULL & xnext-data)p=p-next;s=(ListNode *)malloc(sizeof(ListN

14、ode);s-data=x;s-next=p-next;p-next=s;2有序单链表的插入设单链表L是一个递减有序表，试写一算法将x插入其中后仍保持L的有序性（先把x插入链表头，然后通过交换移动到正确的位置）typedef char DataType;typedef struct nodeDataType data;struct node *next;ListNode;typedef ListNode *LinkList;void InsertSortList(LinkList *L, DataType x)LinkNode *p,*s;DataType t;s=(ListNode *)ma

15、lloc(sizeof(ListNode);s-data=x;s-next=*L;*L=s;p=*L;while (p-next!=NULL & p-datap-next-data)t=p-data;p-data=p-next-data;p-next-data=t;p=p-next;2单链表的合并已知L1和L2分别指向两个单链表的头结点，且已知其长度分别为m和n。试写一算法将这两个链表连接在一起typedef char DataType;typedef struct nodeDataType data;struct node *next;ListNode;typedef ListNode *L

16、inkList;void MergeList(LinkList *L1, LinkList *L2, Linklist *L3)LinkNode *r,*p,*q,*s;*L3=(LinkList)malloc(sizeof(Lnode);r=*L3; p=*L1; q=*L2;while (p | q) if (p)s=(LinkList)malloc(sizeof(Lnode); s-data=p-data;r-next=s;r=s;p=p-next;if (q)s=(LinkList)malloc(sizeof(Lnode);s-data=q-data;r-next=s;r=s;q=q-next;r-next=NULL;*L3=(*L3)-next;2有序单链表的合并设A和B是两个单链表，其表中元素递增有序。试写一算法将A和B归并成一个按元素值递增有序的单链表Ctypedef char DataType;typedef struct nodeDataType data;struct node *next;ListNo