通过代码快速上手C语言数据结构-线性表

左手的ㄟ右手 2023-01-15 11:26 156阅读 0赞

**目录**

2.1顺序表的查找运算

2.2顺序表的插入运算

解析：在顺序表L中第i个数据元素之前插入一个元素e。 插入前表长n=L->last+1，i的合法取值范围是 1≤i≤L->last+2

2.3顺序表的删除运算

解析：在顺序表L中删除第i个数据元素，并用指针参数e返回其值。i的合法取值为1≤i≤L.last+1

2.4顺序表的合并运算

解析：有两个顺序表 LA 和 LB，其元素均为递增有序排列，编写一个算法，将它们合并成一个递增有序顺序表 LC

2.5单链表的初始化

2.6头插法建立单链表

方法1

方法2

解析： 头插法建立单链表

2.7尾插法建立单链表

解析：尾插法建立单链表

2.8单链表按序号查找

解析：在带头结点的单链表L中查找第i个结点，若找到(1≤i≤n)，则返回该结点的存储位置; 否则返回NULL

2.9单链表的按值查找

解析：在带头结点的单链表L中查找其结点值等于key的结点，若找到则返回该结点的位置p，否则返回NULL

2.10求单链的表长度

解析：用计数器遍历

2.11单链表的插入运算

解析：在带头结点的单链表L中第i个位置插入值为e的新结点

2.12单链表的删除运算

解析：在带头结点的单链表L中删除第i个元素，并将删除的元素保存到变量\*e中

2.13单链表的有序合并

解析：将递增有序的单链表LA和LB合并成一个递增有序的单链表LC

2.14循环链表的合并

解析：将两个采用头指针的循环单链表的首尾连接起来

2.15循环链表的合并2

解析：此算法将两个采用尾指针的循环链表首尾连接起来

2.16双向链表的插入运算

解析：双向链表在位置i插入元素e

2.17双向链表的删除运算

解析：双向链表在位置i删除元素e

2.18-2.20静态单链表

2.18静态单链表的初始化

2.19静态单链表的分配结点

2.20静态单链表的结点回收

2.21-2.22多项式

2.21建立—元多项式链表

2.22多项式相加运算

2.23调整顺序表为奇数在左半部分偶数在右半部分

2.24带头结点单链表的就地逆置

2.25单链表实现二进制数加1运算

--------------------

# 2.1顺序表的查找运算 #

#include <stdio.h>
    #include <stdlib.h>
    #include <malloc.h>
    
    #define OK   1
    #define ERROR  0
    #define TRUE 1
    #define FALSE 0
    
    #define ElemType int
    #define	MAXSIZE  100   /*此处的宏定义常量表示线性表可能达到的最大长度*/
    typedef  struct
    { 
    	ElemType  elem[MAXSIZE];  /*线性表占用的数组空间*/
    	int       last;    /*记录线性表中最后一个元素在数组elem[ ]中的位置（下标值），空表置为-1*/
    }SeqList;
    
    int  Locate(SeqList L, ElemType e)
    {	
    	int i=0;        /*i为扫描计数器，初值为0，即从第一个元素开始比较*/
    	while ((i<=L.last)&&(L.elem[i]!=e))		/*顺序扫描表，直到找到值为key的元素, 或扫描到表尾而没找到*/
    		i++; 
    	if  (i<=L.last)
    		return(i+1);  /*若找到值为e的元素，则返回其序号*/
    	else
    		return(-1);  /*若没找到，则返回空序号*/
    }
    
    void main()
    {
    	SeqList l;
    	int p,q,r;
    	int i;
    	printf("请输入线性表的长度:");
    	scanf("%d",&r);
    	l.last = r-1;
    	printf("请输入线性表的各元素值:\n");
    	for(i=0; i<=l.last; i++)
    	{
    		scanf("%d",&l.elem[i]);
    	}
    	printf("请输入要查找的元素值:\n");
    	scanf("%d",&q);
    	p=Locate(l,q);
    	if(p == -1)
    		printf("在此线性表中没有该元素!\n");
    	else
    		printf("该元素在线性表中的位置为:%d\n",p);
    }

# 2.2顺序表的插入运算 #

#include <stdio.h>
    #include <stdlib.h>
    #include <malloc.h>
    
    #define OK   1
    #define ERROR  0
    #define TRUE 1
    #define FALSE 0
    
    #define ElemType int
    #define	MAXSIZE  100   /*此处的宏定义常量表示线性表可能达到的最大长度*/
    typedef  struct
    { 
    	ElemType  elem[MAXSIZE];  /*线性表占用的数组空间*/
    	int       last;    /*记录线性表中最后一个元素在数组elem[ ]中的位置（下标值），空表置为-1*/
    }SeqList;
    /*在顺序表L中第i个数据元素之前插入一个元素e。 插入前表长n=L->last+1，
    i的合法取值范围是 1≤i≤L->last+2  */
    int  InsList(SeqList *L,int i,ElemType e)
    { 
    	int k;
    	if((i<1) || (i>L->last+2)) /*首先判断插入位置是否合法*/
    	{
    		printf("插入位置i值不合法");
    		return(ERROR);
    	}
    	if(L->last>= MAXSIZE-1)
    	{
    		printf("表已满无法插入");
    		return(ERROR);
    	}
    	for(k=L->last;k>=i-1;k--)   /*为插入元素而移动位置*/
    		L->elem[k+1]=L->elem[k];
    	L->elem[i-1]=e;   /*在C语言数组中，第i个元素的下标为i-1*/
    	L->last++;
    	return(OK);
    }
    
    
    void main()
    {
    	SeqList *l;
    	int p,q,r;
    	int i;
    	l=(SeqList*)malloc(sizeof(SeqList));
    	printf("请输入线性表的长度:");
    	scanf("%d",&r);
    	l->last = r-1;
    	printf("请输入线性表的各元素值:\n");
    	for(i=0; i<=l->last; i++)
    	{
    		scanf("%d",&l->elem[i]);
    	}
    	printf("请输入要插入的位置:\n");
    	scanf("%d",&p);
    	printf("请输入要插入的元素值:\n");
    	scanf("%d",&q);
    	InsList(l,p,q);
    	for(i=0; i<=l->last; i++)
    	{
    		printf("%d  ",l->elem[i]);
    	}
    }

### 解析：在顺序表L中第i个数据元素之前插入一个元素e。 插入前表长n=L->last+1，i的合法取值范围是 1≤i≤L->last+2 ###

# 2.3顺序表的删除运算 #

#include <stdio.h>
    #include <stdlib.h>
    #include <malloc.h>
    
    #define OK   1
    #define ERROR  0
    #define TRUE 1
    #define FALSE 0
    
    #define ElemType int
    #define	MAXSIZE  100   /*此处的宏定义常量表示线性表可能达到的最大长度*/
    typedef  struct
    { 
    	ElemType  elem[MAXSIZE];  /*线性表占用的数组空间*/
    	int       last;    /*记录线性表中最后一个元素在数组elem[ ]中的位置（下标值），空表置为-1*/
    }SeqList;
    int  DelList(SeqList *L,int i,ElemType *e)
    /*在顺序表L中删除第i个数据元素，并用指针参数e返回其值。i的合法取值为1≤i≤L.last+1 */    
    { 
    	int k;
    	if((i<1)||(i>L->last+1))   
    	{ 
    		printf("删除位置不合法!");
    		return(ERROR);
    	}
    	*e = L->elem[i-1];  /* 将删除的元素存放到e所指向的变量中*/
    	for(k=i; i<=L->last; k++)
    		L->elem[k-1] = L->elem[k];  /*将后面的元素依次前移*/
    	L->last--;
    	return(OK);
    }
    
    void main()
    {
    	SeqList *l;
    	int p,r;
    	int *q;
    	int i;
    	l = (SeqList*)malloc(sizeof(SeqList));
    	q = (int*)malloc(sizeof(int));
    	printf("请输入线性表的长度:");
    	scanf("%d",&r);
    	l->last = r-1;
    	printf("请输入线性表的各元素值:\n");
    	for(i=0; i<=l->last; i++)
    	{
    		scanf("%d",&l->elem[i]);
    	}
    	printf("请输入要删除的元素位置:\n");
    	scanf("%d",&p);
    	DelList(l,p,q);
    	printf("删除的元素值为:%d\n",*q);
    }

### 解析：在顺序表L中删除第i个数据元素，并用指针参数e返回其值。i的合法取值为1≤i≤L.last+1 ###

# 2.4顺序表的合并运算 #

#include <stdio.h>
    #include <stdlib.h>
    #include <malloc.h>
    
    #define OK   1
    #define ERROR  0
    #define TRUE 1
    #define FALSE 0
    
    #define ElemType int
    #define	MAXSIZE  100   /*此处的宏定义常量表示线性表可能达到的最大长度*/
    typedef  struct
    { 
    	ElemType  elem[MAXSIZE];  /*线性表占用的数组空间*/
    	int       last;    /*记录线性表中最后一个元素在数组elem[ ]中的位置（下标值），空表置为-1*/
    }SeqList;
    void	merge(SeqList *LA,  SeqList *LB,  SeqList *LC)
    {
    	int i,j,k;
    	i=0;j=0;k=0;
    	while(i<=LA->last&&j<=LB->last)
    		if(LA->elem[i]<=LB->elem[j])
    		{
    			LC->elem[k]= LA->elem[i];
    			i++; 
    			k++;
    		}
    		else
    		{
    			LC->elem[k]=LB->elem[j];
    			j++; 
    			k++;
            }
    	while(i<=LA->last)	/*当表LA有剩余元素时，则将表LA余下的元素赋给表LC*/
    	{
    		LC->elem[k]= LA->elem[i];
    		i++; 
    		k++;
    	}
    	while(j<=LB->last)  /*当表LB有剩余元素时，则将表LB余下的元素赋给表LC*/	
    	{
    		LC->elem[k]= LB->elem[j];
    		j++; 
    		k++;
    	}
    	LC->last=LA->last+LB->last+1;
    }
    
    
    void main()
    {
    	SeqList *la,*lb,*lc;
    	int r;
    	int i;
    	la=(SeqList*)malloc(sizeof(SeqList));
    	printf("请输入线性表A的长度:");
    	scanf("%d",&r);
    	la->last = r-1;
    	printf("请输入线性表A的各元素值:\n");
    	for(i=0; i<=la->last; i++)
    	{
    		scanf("%d",&la->elem[i]);
    	}
    	lb=(SeqList*)malloc(sizeof(SeqList));
    	printf("请输入线性表B的长度:");
    	scanf("%d",&r);
    	lb->last = r-1;
    	printf("请输入线性表B的各元素值:\n");
    	for(i=0; i<=lb->last; i++)
    	{
    		scanf("%d",&lb->elem[i]);
    	}
    
    	lc=(SeqList*)malloc(sizeof(SeqList));
    
    	merge(la,lb,lc);
    	printf("合并后线性表C中的元素为:\n");
    	for(i=0; i<=lc->last; i++)
    	{
    		printf("%d  ",lc->elem[i]);
    	}
    }

### 解析：有两个顺序表 LA 和 LB，其元素均为递增有序排列，编写一个算法，将它们合并成一个递增有序顺序表 LC ###

# 2.5单链表的初始化 #

# 2.6头插法建立单链表 #

### 方法1 ###

#include <stdio.h>
    #include <stdlib.h>
    #include <malloc.h>
    
    #define OK   1
    #define ERROR  0
    #define TRUE 1
    #define FALSE 0
    
    typedef char ElemType;
    typedef struct Node    /*结点类型定义*/ 
    { 
    	ElemType data;
    	struct Node  * next;
    }Node, *LinkList;  /* LinkList为结构指针类型*/
    
    #include <stdio.h>
    #include <stdlib.h>
    
    #define ElemType char
    typedef struct Node    /*结点类型定义*/ 
    { 
    	ElemType data;
    	struct Node  * next;
    }Node, *LinkList;  /* LinkList为结构指针类型*/
    
    
    LinkList  CreateFromHead()
    /*通过键盘输入表中元素值，利用头插法建单链表,并返回该单链表头指针L*/
    { 
    	LinkList   L;
    	Node   *s;
    	char 	c;
    	int 	flag=1;
    	L=(LinkList)malloc(sizeof(Node));     /*建立头结点*/
    	L->next=NULL;                         /*建立空的单链表L*/
    	while(flag)   /* flag初值为1，当输入"$"时，置flag为0，建表结束*/
    	{
    		c=getchar();   
    		if(c!='$')
    		{
    			s=(Node*)malloc(sizeof(Node)); /*建立新结点s*/
    			s->data=c;
    			s->next=L->next;/*将s结点插入表头*/
    			L->next=s;
    		}
    		else
    			flag=0;
    	}
    	return L;
    }
    
    void main()
    {
    	LinkList l;
    	Node *p;
    	printf("用头插法建立单链表,请输入链表数据,以$结束!\n");
    	l = CreateFromHead();
    	p = l->next;
    	while(p!=NULL)
    	{
    		printf("%c\n",p->data);
    		p=p->next;
    	}
    }

### 方法2 ###

#include <stdio.h>
    #include <stdlib.h>
    #include <malloc.h>
    
    #define OK   1
    #define ERROR  0
    #define TRUE 1
    #define FALSE 0
    
    typedef char ElemType;
    typedef struct Node    /*结点类型定义*/ 
    { 
    	ElemType data;
    	struct Node  * next;
    }Node, *LinkList;  /* LinkList为结构指针类型*/
    
    #include "common.h"
    #include "linklist.h"
    
    void init_linklist(LinkList *l)/*对单链表进行初始化*/
    {
    	*l=(LinkList)malloc(sizeof(Node)); 
    	(*l)->next=NULL;
    }
    
    
    void CreateFromHead(LinkList  L)
    { 
    	Node   *s;
    	char 	c;
    	int 	flag=1;
     	while(flag)   /* flag初值为1，当输入"$"时，置flag为0，建表结束*/
    	{
    		c=getchar();   
    		if(c!='$')
    		{
    			s=(Node*)malloc(sizeof(Node)); /*建立新结点s*/
    			s->data=c;
    			s->next=L->next;/*将s结点插入表头*/
    			L->next=s;
    		}
    		else
    			flag=0;
    	}
    }
    
    void main()
    {
    	LinkList l;
    	Node *p;
    	init_linklist(&l);
    	printf("用头插法建立单链表,请输入链表数据,以$结束!\n");
    	CreateFromHead(l);
    	p = l->next;
    	while(p!=NULL)
    	{
    		printf("%c\n",p->data);
    		p=p->next;
    	}
    }

### 解析： 头插法建立单链表 ###

# 2.7尾插法建立单链表 #

### 解析：尾插法建立单链表 ###

# 2.8单链表按序号查找 #

#include <stdio.h>
    #include <stdlib.h>
    #include <malloc.h>
    
    #define OK   1
    #define ERROR  0
    #define TRUE 1
    #define FALSE 0
    
    typedef char ElemType;
    typedef struct Node    /*结点类型定义*/ 
    { 
    	ElemType data;
    	struct Node  * next;
    }Node, *LinkList;  /* LinkList为结构指针类型*/
    Node * Get (LinkList  L, int i)
    /*在带头结点的单链表L中查找第i个结点，若找到(1≤i≤n)，则返回该结点的存储位置; 否则返回NULL*/
    {  
    	int j;
    	Node  *p;
    	p=L;
    	j=0;   /*从头结点开始扫描*/ 
    	while ((p->next!=NULL)&&(j<i))
    	{ 
    		p=p->next;    /* 扫描下一结点*/
    		j++;   /* 已扫描结点计数器 */
    	}
    	if(i == j)
    		return p;   /* 找到了第i个结点 */
    	else 
    		return NULL;   /* 找不到，i≤0或i>n */
    }   
    
    
    void main()
    {
    	LinkList l;
    	Node *p;
    	int j;
    	init_linklist(&l);
    	printf("请输入链表数据,以$结束!\n");
    	CreateFromTail(l);
    	p = l->next;
    	while(p!=NULL)
    	{
    		printf("%c\n",p->data);
    		p=p->next;
    	}
    	printf("请输入要查找的结点序号:\n");
    	scanf("%d",&j);
    	p = Get(l,j);
    	if(p!=NULL)
    		printf("该结点的值为:%c\n",p->data);
    	else
    		printf("未找到此结点!\n");
    }

### 解析：在带头结点的单链表L中查找第i个结点，若找到(1≤i≤n)，则返回该结点的存储位置; 否则返回NULL ###

# 2.9单链表的按值查找 #

### 解析：在带头结点的单链表L中查找其结点值等于key的结点，若找到则返回该结点的位置p，否则返回NULL ###

# 2.10求单链的表长度 #

### 解析：用计数器遍历 ###

# 2.11单链表的插入运算 #

#include <stdio.h>
    #include <stdlib.h>
    #include <malloc.h>
    
    #define OK   1
    #define ERROR  0
    #define TRUE 1
    #define FALSE 0
    
    typedef char ElemType;
    typedef struct Node    /*结点类型定义*/ 
    { 
    	ElemType data;
    	struct Node  * next;
    }Node, *LinkList;  /* LinkList为结构指针类型*/
    int InsList(LinkList L,int i,ElemType e)
    /*在带头结点的单链表L中第i个位置插入值为e的新结点s*/
    {  
    	Node *pre,*s;
    	int k;
    	pre=L;  
    	k=0;                     /*从"头"开始，查找第i-1个结点*/
    	while(pre!=NULL&&k<i-1)  /*表未查完且未查到第i-1个时重复，找到pre指向第i-1个*/ 
    	{ 
    		pre=pre->next;
    		k=k+1; 
    	}									/*查找第i-1结点*/
    	if(!pre)      /*如当前位置pre为空表已找完还未数到第i个，说明插入位置不合理*/ 
    	{ 
    		printf("插入位置不合理!");
    		return ERROR;
    	}
    	s=(Node*)malloc(sizeof(Node));   /*申请一个新的结点S */
    	s->data=e;                       /*值e置入s的数据域*/
    	s->next=pre->next;				/*修改指针，完成插入操作*/
    	pre->next=s;
    	return OK;
    }
    
    void main()
    {
    	LinkList l;
    	Node *p;
    	int flag=0;
    	int i;
    	char c;
    	init_linklist(&l);		
    	printf("请输入链表数据,以$结束!\n");
    	CreateFromTail(l);
    	p = l->next;
    	while(p!=NULL)
    	{
    		printf("%c\n",p->data);
    		p=p->next;
    	}
    	printf("请输入插入的位置和元素:\n");
    	scanf("%d,%c",&i,&c);
    	flag=InsList(l, i, c);
    	if(flag)
    		printf("插入操作成功!\n");
    	else
    		printf("插入操作失败!\n");
    	p = l->next;
    	while(p!=NULL)
    	{
    		printf("%c\n",p->data);
    		p=p->next;
    	}
    }

### 解析：在带头结点的单链表L中第i个位置插入值为e的新结点 ###

# 2.12单链表的删除运算 #

#include <stdio.h>
    #include <stdlib.h>
    #include <malloc.h>
    
    #define OK   1
    #define ERROR  0
    #define TRUE 1
    #define FALSE 0
    
    typedef char ElemType;
    typedef struct Node    /*结点类型定义*/ 
    { 
    	ElemType data;
    	struct Node  * next;
    }Node, *LinkList;  /* LinkList为结构指针类型*/
    int DelList(LinkList L,int i,ElemType *e)
    /*在带头结点的单链表L中删除第i个元素，并将删除的元素保存到变量*e中*/
    {  
    	Node *pre,*r;
    	int k;
    	pre=L;
    	k=0;
    	while(pre->next!=NULL && k<i-1)	/*寻找被删除结点i的前驱结点i-1使p指向它*/
    	{ 
    		pre=pre->next; 
    		k=k+1;
    	}								/*查找第i-1个结点*/
    	if(!(pre->next))     /* 即while循环是因为p->next=NULL或i<1而跳出的,而是因为没有找到合法的前驱位置，说明删除位置i不合法。*/
    	{
    		printf("删除结点的位置i不合理!");
    		return ERROR;
    	}
    	r=pre->next;
    	pre->next=pre->next->next;    /*修改指针，删除结点r*/
    	*e = r->data;
    	free(r);    /*释放被删除的结点所占的内存空间*/
    	printf("成功删除结点!");
    	return OK;
    }
    
    void main()
    {
    	LinkList l;
    	Node *p;
    	int i;
    	char *c;
    	l=(Node * )malloc(sizeof(Node));     
    	l->next=NULL; 		
    	printf("请输入链表数据,以$结束!\n");
    	CreateFromTail(l);
    	p = l->next;
    	while(p!=NULL)
    	{
    		printf("%c\n",p->data);
    		p=p->next;
    	}
    	i = 3;
    	c = (char*)malloc(sizeof(char));
    	DelList(l,i,c);
    	printf("被删除的元素是:%c\n",*c);
    }

### 解析：在带头结点的单链表L中删除第i个元素，并将删除的元素保存到变量\*e中 ###

# 2.13单链表的有序合并 #

#include <stdio.h>
    #include <stdlib.h>
    #include <malloc.h>
    
    #define OK   1
    #define ERROR  0
    #define TRUE 1
    #define FALSE 0
    
    typedef char ElemType;
    typedef struct Node    /*结点类型定义*/ 
    { 
    	ElemType data;
    	struct Node  * next;
    }Node, *LinkList;  /* LinkList为结构指针类型*/
    LinkList MergeLinkList(LinkList LA, LinkList LB)
    /*将递增有序的单链表LA和LB合并成一个递增有序的单链表LC*/
    {  
    	Node *pa,*pb;
    	Node *r;
    	LinkList LC;
    /*将LC初始置空表。pa和pb分别指向两个单链表LA和LB中的第一个结点,r初值为LC*/
    	pa=LA->next;
    	pb=LB->next;
    	LC=LA;
    	LC->next=NULL;
    	r=LC;
    /*当两个表中均未处理完时，比较选择将较小值结点插入到新表LC中。*/
    	while(pa!=NULL && pb!=NULL)
    	{
    		if(pa->data <= pb->data)
    		{
    			r->next=pa;
    			r=pa;
    			pa=pa->next;
    		}
    		else
    		{
    			r->next=pb;
    			r=pb;
    			pb=pb->next;
    		}
    	}
    	if(pa) /*若表LA未完，将表LA中后续元素链到新表LC表尾*/
    		r->next=pa;
    	else	 /*否则将表LB中后续元素链到新表LC表尾*/
    		r->next=pb;
    	free(LB);
    	return(LC);
    }
    
    
    void main()
    {
    	LinkList la,lb,lc;
    	Node *p;
    	la=(Node * )malloc(sizeof(Node));     
    	la->next=NULL; 
    	printf("请输入单链表A中的元素(以-1结束!):\n");
    	CreateFromTail(la);
    	printf("单链表A中元素为:\n");
    	p = la->next;
    	while(p!=NULL)
    	{
    		printf("%d   ",p->data);
    		p=p->next;
    	}
    	printf("\n");
    
    	printf("请输入单链表B中的元素(以-1结束!):\n");
    	lb=(Node * )malloc(sizeof(Node));     
    	lb->next=NULL; 
    	CreateFromTail(lb);
    	printf("单链表B中元素为:\n");
    	p = lb->next;
    	while(p!=NULL)
    	{
    		printf("%d   ",p->data);
    		p=p->next;
    	}
    	printf("\n");
    
    	lc=MergeLinkList(la,lb);
    	printf("单链表C中元素为:\n");
    	p = lc->next;
    	while(p!=NULL)
    	{
    		printf("%d   ",p->data);
    		p=p->next;
    	}
    }

### 解析：将递增有序的单链表LA和LB合并成一个递增有序的单链表LC ###

# 2.14循环链表的合并 #

#include <stdio.h>
    #include <stdlib.h>
    #include <malloc.h>
    
    #define OK   1
    #define ERROR  0
    #define TRUE 1
    #define FALSE 0
    
    
    typedef int ElemType;
    typedef struct Node    /*结点类型定义*/ 
    { 
    	ElemType data;
    	struct Node  * next;
    }Node, *LinkList;  /* LinkList为结构指针类型*/
    
    void create_clinklist(LinkList l)/*创建循环链表*/
    {
    	int num;
    	Node *p;
    	l->data=-1;
    	l->next=l;
    	printf("请输入循环链表的元素 (以-1结束):\n");
    	scanf("%d",&num);
    	while(num != -1)
    	{
    		p=(Node*)malloc(sizeof(struct Node));
    		p->data=num;
    		p->next=l->next;
    		l->next=p;
    		scanf("%d",&num);
    	}
    }
    
    LinkList   merge_1(LinkList LA,LinkList LB)
    {  /*此算法将两个采用头指针的循环单链表的首尾连接起来*/
    	Node *p, *q;
    	p=LA;
    	q=LB;
    	while (p->next!=LA)	p=p->next;	/*找到表LA的表尾，用p指向它*/
    	while (q->next!=LB)	q=q->next;	/*找到表LB的表尾，用q指向它*/
    	q->next=LA;	/*修改表LB 的尾指针，使之指向表LA 的头结点*/
    	p->next=LB->next; /*修改表LA的尾指针，使之指向表LB 中的第一个结点*/
    	free(LB);
    	return(LA);
    }
    
    
    void main()
    {
    	LinkList la,lb,lc;
    	Node *p;
    	printf("建立循环链表A，请输入数据!:\n");
    	la=(Node*)malloc(sizeof(struct Node));
    	create_clinklist(la);
    	p = la->next;
    	while(p!=la)
    	{
    		printf("%d\n",p->data);
    		p=p->next;
    	}
    	printf("建立循环链表B，请输入数据!:\n");
    	lb=(Node*)malloc(sizeof(struct Node));
    	create_clinklist(lb);
    	p = lb->next;
    	while(p!=lb)
    	{
    		printf("%d\n",p->data);
    		p=p->next;
    	}
    	lc=merge_1(la,lb);
    	printf("合并后的循环链表为:\n");
    	p = lc->next;
    	while(p!=lc)
    	{
    		printf("%d\n",p->data);
    		p=p->next;
    	}
    }

### 解析：将两个采用头指针的循环单链表的首尾连接起来 ###

# 2.15循环链表的合并2 #

#include <stdio.h>
    #include <stdlib.h>
    #include <malloc.h>
    
    #define OK   1
    #define ERROR  0
    #define TRUE 1
    #define FALSE 0
    
    
    typedef int ElemType;
    typedef struct Node    /*结点类型定义*/ 
    { 
    	ElemType data;
    	struct Node  * next;
    }Node, *LinkList;  /* LinkList为结构指针类型*/
    
    void create_clinklist(LinkList l)/*创建循环链表*/
    {
    	int num;
    	Node *p;
    	l->data=-1;
    	l->next=l;
    	printf("请输入循环链表的元素 (以-1结束):\n");
    	scanf("%d",&num);
    	while(num != -1)
    	{
    		p=(Node*)malloc(sizeof(struct Node));
    		p->data=num;
    		p->next=l->next;
    		l->next=p;
    		scanf("%d",&num);
    	}
    }
    
    LinkList  merge_2(LinkList RA,LinkList RB)
    {  /*此算法将两个采用尾指针的循环链表首尾连接起来*/
    	Node *p;
    	p=RA->next; /*保存链表RA的头结点地址*/
    	RA->next=RB->next->next;/*链表RB的开始结点链到链表RA的终端结点之后*/
    	free(RB->next);/*释放链表RB的头结点*/
    	RB->next=p;/*链表RA的头结点链到链表RB的终端结点之后*/
        return  RB;/*返回新循环链表的尾指针*/
    }
    
    void main()
    {
    	LinkList la,lb,lc;
    	Node *p;
    	printf("建立循环链表A，请输入数据!:\n");
    	la=crt_linklist();
    	p = la->next->next;
    	while(p!=la->next)
    	{
    		printf("%d\n",p->data);
    		p=p->next;
    	}
    	printf("建立循环链表B，请输入数据!:\n");
    	lb=crt_linklist();
    	p = lb->next->next;
    	while(p!=lb->next)
    	{
    		printf("%d\n",p->data);
    		p=p->next;
    	}
    	lc=merge_2(la,lb);
    	printf("合并后的循环链表为:\n");
    	p = lc->next->next;
    	while(p!=lc->next)
    	{
    		printf("%d\n",p->data);
    		p=p->next;
    	}
    }

### 解析：此算法将两个采用尾指针的循环链表首尾连接起来 ###

# 2.16双向链表的插入运算 #

#include <stdio.h>
    #include <stdlib.h>
    #include <malloc.h>
    
    #define OK   1
    #define ERROR  0
    #define TRUE 1
    #define FALSE 0
    
    typedef char ElemType;
    
    typedef struct DNode
    {
    	ElemType data;
    	struct DNode *prior, *next;
    }DNode,	*DoubleList;
    
    void CreateList(DoubleList L)
    /*通过键盘输入表中元素值，利用尾插法建单链表,并返回该单链表头指针L*/
    { 
    	DNode *r, *s;
    	char c;
    	int   flag =1; /*设置一个标志，初值为1，当输入"$"时，flag为0，建表结束*/
    	L->next=L;
    	L->prior=L;
    	r=L;              
    	while(flag)         
    	{
    		c=getchar();
    		if(c!='$')
    		{
    			s=(DNode*)malloc(sizeof(DNode));
    			s->data=c;
    			r->next=s;
    			s->prior=r;
    			r=s;
    		}
    		else
    		{
    			flag=0;
    			r->next=L;   
    			L->prior=r;
    		}
    	}   /*while*/
    } 
    int DlinkIns(DoubleList L,int i,ElemType e)
    {
    	DNode  *s,*p;
    	int k;
    	p=L;  
    	k=0;                     /*从"头"开始，查找第i-1个结点*/
    	while(p->next!=L&&k<i)  /*表未查完且未查到第i-1个时重复，找到p指向第i个*/ 
    	{ 
    		p=p->next;
    		k=k+1; 
    	}									/*查找第i-1结点*/
    	if(p->next == L)      /*如当前位置p为空表已找完还未数到第i个，说明插入位置不合理*/ 
    	{ 
    		printf("插入位置不合理!");
    		return ERROR;
    	}
    	s=(DNode*)malloc(sizeof(DNode));
     	if (s)
    	{
    		s->data=e;
    		s->prior=p->prior;		
    		p->prior->next=s;	
    		s->next=p;			
    		p->prior=s;			
    		return OK;
    	}
    	else 
    		return ERROR;
    }
    
    void main()
    {
    	DoubleList l;
    	DNode *p;
    	int i;
    	char e;
    	l=(DNode * )malloc(sizeof(DNode));
    	printf("请输入双向链表数据!:\n");
    	CreateList(l);
    	p = l->next;
    	while(p!=l)
    	{
    		printf("%c\n",p->data);
    		p=p->next;
    	}
    	printf("情输入插入位置和元素值:\n");
    	scanf("%d,%c",&i,&e);
    	DlinkIns(l,i,e);
    	printf("插入后的链表为:\n");
    	p = l->next;
    	while(p!=l)
    	{
    		printf("%c\n",p->data);
    		p=p->next;
    	}
    }

### 解析：双向链表在位置i插入元素e ###

# 2.17双向链表的删除运算 #

#include <stdio.h>
    #include <stdlib.h>
    #include <malloc.h>
    
    #define OK   1
    #define ERROR  0
    #define TRUE 1
    #define FALSE 0
    
    typedef char ElemType;
    
    typedef struct DNode
    {
    	ElemType data;
    	struct DNode *prior, *next;
    }DNode,	*DoubleList;
    
    void CreateList(DoubleList L)
    /*通过键盘输入表中元素值，利用尾插法建单链表,并返回该单链表头指针L*/
    { 
    	DNode *r, *s;
    	char c;
    	int   flag =1; /*设置一个标志，初值为1，当输入"$"时，flag为0，建表结束*/
    	L->next=L;
    	L->prior=L;
    	r=L;              
    	while(flag)         
    	{
    		c=getchar();
    		if(c!='$')
    		{
    			s=(DNode*)malloc(sizeof(DNode));
    			s->data=c;
    			r->next=s;
    			s->prior=r;
    			r=s;
    		}
    		else
    		{
    			flag=0;
    			r->next=L;   
    			L->prior=r;
    		}
    	}   /*while*/
    } 
    int	DlinkDel(DoubleList L,int i,ElemType *e)
    {
    	DNode  *p;
    	int k;
    	p=L;  
    	k=0;                     /*从"头"开始，查找第i个结点*/
    	while(p->next!=L && k<i)  /*表未查完且未查到第i个时重复，找到p指向第i个*/ 
    	{ 
    		p=p->next;
    		k=k+1; 
    	}								
    	if(p->next == L)       
    	{ 
    		return ERROR;
    	}
    	else
    	{
    		*e=p->data;
    		p->prior->next=p->next;
    		p->next->prior=p->prior;
    		free(p);
    		return OK;
    	}
    }
    
    
    void main()
    {
    	DoubleList l;
    	DNode *p;
    	int i;
    	int flag=0;
    	char *e;
    	l=(DNode * )malloc(sizeof(DNode));
    	printf("请输入链表数据:\n");
    	CreateList(l);
    	p = l->next;
    	while(p!=l)
    	{
    		printf("%c\n",p->data);
    		p=p->next;
    	}
    	printf("请输入要删除的位置:\n");
    	scanf("%d",&i);
    	e=(char *)malloc(sizeof(char));
    	flag=DlinkDel(l,i,e);
    	if(flag == 1)
    	{
    		printf("删除的元素是:%c\n",*e);
    	}
    	else
    		printf("删除位置不合理!");
    }

### 解析：双向链表在位置i删除元素e ###

# 2.18-2.20静态单链表 #

## 2.18静态单链表的初始化 ##

## 2.19静态单链表的分配结点 ##

## 2.20静态单链表的结点回收 ##

#include<stdio.h>
    #include<stdlib.h>
    
    #define  Maxsize 100
    #define  ElemType char
    
    typedef  struct
    {	
    	ElemType data;
    	int cursor;
    }Component, StaticList[Maxsize];
    
    void initial(StaticList space, int *av)
    {
        int k;
    	space[0].cursor=0;      /*设置已用静态单链表的头指针指向位置0*/
    	for(k=0;k<Maxsize-1;k++)
    		space[k].cursor=k+1;    /*连链*/
    	space[Maxsize-1].cursor=0;    /*标记链尾*/
    	*av=1;  /*设置备用链表头指针初值*/
    }
    
    int getnode(StaticList space, int *av)
    /*从备用链表摘下一个结点空间，分配给待插入静态链表中的元素*/
    {
    	int i;
    	i=*av;
    	*av=space[*av].cursor;
    	return i;
    }
    
    void   freenode(StaticList space, int *av, int k)
    /*将下标为 k的空闲结点插入到备用链表*/
    {
    	space[k].cursor=*av;
    	*av=k;
    }
    
    void  insbefore(StaticList space,int i,int *av, char x)
    {
    	int j,k,m;
    	j=getnode(space,av);	               
    	space[j].data=x;	
    	k=space[0].cursor;      /* k 为已用静态单链表的第一个元素的下标值*/
    	for(m=1;m<i-1;m++)		      /*寻找第i -1个元素的位置k */
    		k=space[k].cursor;
    	space[j].cursor=space[k].cursor; /*修改游标域，实现插入操作*/
    	space[k].cursor=j;
    }/*insbefore*/
    
    
    void deleteelem(StaticList space, int i, int *av)
    { 
    	int j,k,m;
    	k=space[0].cursor;
    	for(m=1;m<i-1;m++)	/*寻找第i-1个元素的位置k */
    		k=space[k].cursor;
    	j=space[k].cursor;
    	space[k].cursor=space[j].cursor ;	/*从已用表中删除第i 个元素*/
    	freenode(space, av, j);
    }
    
    void output(StaticList space)
    {
    	int i;
    	i= 1;
    	while(space[i].cursor != 0)
    	{
    		printf("%c  ",space[i].data);
    		i=space[i].cursor;
    	}
    	printf("%c\n",space[i].data);
    }
    
    void main()
    {
    	StaticList sp;
    	int *p;
    	char c;
    	int i,j;
    	p= (int *)malloc(sizeof(int));
    	initial(sp,p);
    	for (i=0; i<5; i++)
    	{
    		j=getnode(sp,p);
    		printf("请输入第%d个数据:",i+1);
    		fflush(stdin);
    		scanf("%c",&c);
    		sp[j].data = c;
    	}
    	sp[j].cursor=0;
    	output(sp);
    	
    	printf("请输入要插入的位置和数据:\n");
    	fflush(stdin);
    	scanf("%d,%c",&i,&c);
    	insbefore(sp,i,p,c);
    	output(sp);
    	
    	printf("请输入要删除的位置\n");
    	fflush(stdin);
    	scanf("%d",&i);
    	deleteelem(sp,i,p);
    	output(sp);
    }

# 2.21-2.22多项式 #

## 2.21建立—元多项式链表 ##

## 2.22多项式相加运算 ##

#include <stdio.h>
    #include <stdlib.h>
    #include <malloc.h>
    
    #define OK   1
    #define ERROR  0
    #define TRUE 1
    #define FALSE 0
    typedef struct Polynode 
    {
    	int coef;
    	int exp;
    	Polynode *next;
    }Polynode, *Polylist;
    
    void polycreate(Polylist head)
    {
    	Polynode *rear, *s;
    	int c,e;
    	rear=head;	                            /* rear 始终指向单链表的尾，便于尾插法建表*/
    	scanf("%d,%d",&c,&e);                   /*键入多项式的系数和指数项*/
    	while(c!=0)	                            /*若c=0，则代表多项式的输入结束*/
    	{
    		s=(Polynode*)malloc(sizeof(Polynode));	/*申请新的结点*/
    		s->coef=c;
    		s->exp=e;
    		rear->next=s;		/*在当前表尾做插入*/
    		rear=s;
    		scanf("%d,%d",&c,&e); 
    	}
    	rear->next=NULL;	/*将表的最后一个结点的next置NULL，以示表结束*/
    }
    
    void  polyadd(Polylist polya, Polylist polyb)
    /*此函数用于将两个多项式相加，然后将和多项式存放在多项式polya中，并将多项式ployb删除*/
    {
    	Polynode  *p, *q, *pre, *temp;
    	int sum;
    	p=polya->next;   /*令 p和q分别指向polya和polyb多项式链表中的第一个结点*/
    	q=polyb->next;        
    	pre=polya;  /* r指向和多项式的尾结点*/
    	while (p!=NULL && q!=NULL) /*当两个多项式均未扫描结束时*/
    	{ 
    		if  (p->exp < q->exp)
    			/*如果p指向的多项式项的指数小于q的指数，将p结点加入到和多项式中*/
    		{ 
    			pre->next=p;  
    			pre=p; 
    			p=p->next;
    		}
    		else
    			if ( p->exp == q->exp)  /*若指数相等，则相应的系数相加*/
    			{  
    				sum=p->coef + q->coef;
    				if (sum != 0)
    				{ 
    					p->coef=sum;
    					pre->next=p; 
    					pre=p;
    					p=p->next;
    					temp=q; 
    					q=q->next; 
    					free(temp);
    				}
    				else
    				{  
    					temp=p;
    					p=p->next;
    					free(temp); 
    		/*若系数和为零，则删除结点p与q，并将指针指向下一个结点*/
    					temp=q; 
    					q=q->next;
    					free(temp);
    				}
    			}
    			else
    			{  
    				pre->next=q;
    				pre=q; /*将q结点加入到和多项式中*/
    				q = q->next; 
    			}
    	}
    	if(p!=NULL)  /*多项式A中还有剩余，则将剩余的结点加入到和多项式中*/
    		pre->next=p;
    	else      /*否则，将B中的结点加入到和多项式中*/
    		pre->next=q;
    }
       
    void main()
    {
    	Polylist polya,polyb;
    	Polynode *p;
    	printf("请输入数据建立多项式A:(以0,0结束!)\n");
    	polya=(Polynode *)malloc(sizeof(Polynode));
    	polycreate(polya);
    	p = polya->next;
    		while(p!=NULL)
    		{
    			printf("%d   %d\n",p->coef,p->exp);
    			p=p->next;
    		}
    	printf("请输入数据建立多项式B:(以0,0结束!)\n");
    	polyb=(Polynode *)malloc(sizeof(Polynode));
    	polycreate(polyb);
    	p = polyb->next;
    	while(p!=NULL)
    	{
    		printf("%d   %d\n",p->coef,p->exp);
    		p=p->next;
    	}
    	polyadd(polya,polyb);
    	printf("相加后的多项式为:\n");
    	p = polya->next;
    	while(p!=NULL)
    	{
    		printf("%d   %d\n",p->coef,p->exp);
    		p=p->next;
    	}
    
    }

# 2.23调整顺序表为奇数在左半部分偶数在右半部分 #

#include <stdio.h>
    #include <stdlib.h>
    #include <malloc.h>
    
    #define OK   1
    #define ERROR  0
    #define TRUE 1
    #define FALSE 0
    #define ElemType int
    #define	MAXSIZE  100   /*此处的宏定义常量表示线性表可能达到的最大长度*/
    typedef  struct
    { 
    	ElemType  elem[MAXSIZE];  /*线性表占用的数组空间*/
    	int       last;    /*记录线性表中最后一个元素在数组elem[ ]中的位置（下标值），空表置为-1*/
    }SeqList;
    
    void AdjustSqlist(SeqList  *L)
    {
    	int i=0,j=L->last;
    	int temp;
    	while(i<j)
    	{  
    		while(L->elem[i]%2 != 0)
    			i++;   /*从表的左半部分开始检测，若为奇数，则i加1,直到找到偶数为止*/
    	    while(L->elem[j]%2 == 0)
    			j--;      /* 从表的右半部分开始检测，若为偶数，则j减1,直到找到奇数为止*/
    		if(i<j) 
    		{
    			temp = L->elem[i];
    			L->elem[i]= L->elem[j];
    			L->elem[j]=temp;
    		}
    	}
    	
    }
    
    void main()
    {
    	SeqList *l;
    	int r;
    	int i;
    	l=(SeqList*)malloc(sizeof(SeqList));
    	printf("请输入线性表的长度:");
    	scanf("%d",&r);
    	l->last = r-1;
    	printf("请输入线性表的各元素值:\n");
    	for(i=0; i<=l->last; i++)
    	{
    		scanf("%d",&l->elem[i]);
    	}
    	printf("线性表元素为:\n");
    	for(i=0; i<=l->last; i++)
    	{
    		printf("%d  ",l->elem[i]);
    	}
    	AdjustSqlist(l);
    	printf("\n");
    	printf("调整后的线性表元素为:\n");
    	for(i=0; i<=l->last; i++)
    	{
    		printf("%d  ",l->elem[i]);
    	}
    }

# 2.24带头结点单链表的就地逆置 #

#include <stdio.h>
    #include <stdlib.h>
    
    #define ElemType char
    typedef struct Node    /*结点类型定义*/ 
    { 
    	ElemType data;
    	struct Node  * next;
    }Node, *LinkList;  /* LinkList为结构指针类型*/
    
    
    LinkList CreateFromTail()
    /*通过键盘输入表中元素值，利用尾插法建单链表,并返回该单链表头指针L*/
    { 
    	LinkList L;
    	Node *r, *s;
    	char c;
    	int   flag =1; /*设置一个标志，初值为1，当输入"$"时，flag为0，建表结束*/
    	L=(Node * )malloc(sizeof(Node));     
    	L->next=NULL;	 		/*为头结点分配存储空间，建立空的单链表L*/
    	r=L;                /*r指针动态指向链表的当前表尾，以便于做尾插入，其初值指向头结点*/
    	while(flag)         /*循环输入表中元素值，将建立新结点s插入表尾*/
    	{
    		c=getchar();
    		if(c!='$')
    		{
    			s=(Node*)malloc(sizeof(Node));
    			s->data=c;
    			r->next=s;
    			r=s;
    		}
    		else
    		{
    			flag=0;
    			r->next=NULL;   /*将最后一个结点的next链域置为空，表示链表的结束*/
    		}
    	}  
    	return L;
    } 
    
    void  ReverseList(LinkList  L)
    { 
    	Node *p,*q;
    	p=L->next;
    	L->next=NULL;
    	while(p!=NULL)
    	{ 
    		q=p->next;     /*q指针保留p->next得值*/
    		p->next=L->next;
    		L->next=p;    /*将p结点头插入到单链表L中*/
    		p=q;          /*p指向下一个要插入的结点*/
    	} 
    }
    
    void main()
    {
    	LinkList l;
    	Node *p;
    	printf("用尾插法建立单链表,请输入链表数据,以$结束!\n");
        l = CreateFromTail();
    	printf("输入的单链表为:\n");
    	p = l->next;
    	while(p!=NULL)
    	{
    		printf("%c\n",p->data);
    		p=p->next;
    	}
    	ReverseList(l);
    	printf("逆置后的单链表为:\n");
    	p = l->next;
    	while(p!=NULL)
    	{
    		printf("%c\n",p->data);
    		p=p->next;
    	}
    }

#include <stdio.h>
    #include <stdlib.h>
    #include <malloc.h>
    
    #define OK   1
    #define ERROR  0
    #define TRUE 1
    #define FALSE 0
    
    typedef char ElemType;
    typedef struct Node    /*结点类型定义*/ 
    { 
    	ElemType data;
    	struct Node  * next;
    }Node, *LinkList;  /* LinkList为结构指针类型*/
    
    void CreateFromTail(LinkList L)
    { 
    	Node *r, *s;
    	char c;
    	int   flag =1; /*设置一个标志，初值为1，当输入"$"时，flag为0，建表结束*/
    	r=L;                /*r指针动态指向链表的当前表尾，以便于做尾插入，其初值指向头结点*/
    	while(flag)         /*循环输入表中元素值，将建立新结点s插入表尾*/
    	{
    		c=getchar();
    		if(c!='$')
    		{
    			s=(Node*)malloc(sizeof(Node));
    			s->data=c;
    			r->next=s;
    			r=s;
    		}
    		else
    		{
    			flag=0;
    			r->next=NULL;   /*将最后一个结点的next链域置为空，表示链表的结束*/
    		}
    	}   
    } 
    
    
    void  ReverseList(LinkList  L)
    { 
    	Node *p,*q;
    	p=L->next;
    	L->next=NULL;
    	while(p!=NULL)
    	{ 
    		q=p->next;     /*q指针保留p->next得值*/
    		p->next=L->next;
    		L->next=p;    /*将p结点头插入到单链表L中*/
    		p=q;          /*p指向下一个要插入的结点*/
    	} 
    }
    
    void main()
    {
    	LinkList l;
    	Node *p;
    	l=(Node * )malloc(sizeof(Node));
    	l->next = NULL;
    	printf("用尾插法建立单链表,请输入链表数据,以$结束!\n");
        CreateFromTail(l);
    	printf("输入的单链表为:\n");
    	p = l->next;
    	while(p!=NULL)
    	{
    		printf("%c\n",p->data);
    		p=p->next;
    	}
    	ReverseList(l);
    	printf("逆置后的单链表为:\n");
    	p = l->next;
    	while(p!=NULL)
    	{
    		printf("%c\n",p->data);
    		p=p->next;
    	}
    }

# 2.25单链表实现二进制数加1运算 #

#include <stdio.h>
    #include <stdlib.h>
    #include <malloc.h>
    
    #define OK   1
    #define ERROR  0
    #define TRUE 1
    #define FALSE 0
    
    
    typedef int ElemType;
    typedef struct Node    /*结点类型定义*/ 
    { 
    	ElemType data;
    	struct Node  * next;
    }Node, *LinkList;  /* LinkList为结构指针类型*/
    
    void CreateFromTail(LinkList L)
    { 
    	Node *r, *s;
    	char c;
    	int   flag =1; /*设置一个标志，初值为1，当输入"$"时，flag为0，建表结束*/
    	r=L;                /*r指针动态指向链表的当前表尾，以便于做尾插入，其初值指向头结点*/
    	while(flag)         /*循环输入表中元素值，将建立新结点s插入表尾*/
    	{
    		scanf("%d",&c);
    		if(c != -1)
    		{
    			s=(Node*)malloc(sizeof(Node));
    			s->data=c;
    			r->next=s;
    			r=s;
    		}
    		else
    		{
    			flag=0;
    			r->next=NULL;   /*将最后一个结点的next链域置为空，表示链表的结束*/
    		}
    	}   
    } 
    void BinAdd(LinkList l)
    {
    	Node *q,*r,*temp,*s;
    	q=l->next;
    	r=l;
    	while(q!=NULL)
    	{
    		if(q->data == 0)
    			r = q;
    		q = q->next;
    	}
    	if(r != l)
    	{
    		r->data = 1;
    	}
    	else
    	{	
    		temp = r->next;
    		s=(Node*)malloc(sizeof(Node));
    		s->data=1;
    		s->next=temp;
    		r->next = s;
    		r = s;
    	}
    	r = r->next;
    	while(r!=NULL)
    	{
    		r->data = 0;
    		r = r->next;
    	}
    }
    
    
    void main()
    {
    	LinkList la;
    	Node *p;
    	printf("请输入二进制数(以-1结束!):\n");
    	la=(Node * )malloc(sizeof(Node));
    	la->next = NULL;
    	CreateFromTail(la);
    	printf("二进制数为:\n");
    	p = la->next;
    	while(p!=NULL)
    	{
    		printf("%d   ",p->data);
    		p=p->next;
    	}
    	printf("\n");
    	BinAdd(la);
    	printf("加1后的二进制数为:\n");
    	p = la->next;
    	while(p!=NULL)
    	{
    		printf("%d   ",p->data);
    		p=p->next;
    	}
    }