数据结构C语言实现之线性表

#include<stdio.h>
#include<stdlib.h>
typedefintelemType;
/************************************************************************/
/*　　　　　　　　以下是关于线性表顺序存储操作的16种算法　　　　　　　　　　 　*/
/************************************************************************/
structList{
　　 elemType*list;
　　 intsize;
　　 intmaxSize;
};
voidagainMalloc(structList*L)
{　　
　　 /*空间扩展为原来的2倍，并由p指针所指向，原内容被自动拷贝到p所指向的存储空间*/
　　 elemType*p=realloc(L->list,2*L->maxSize*sizeof(elemType));
　　 if(!p){　　/*分配失败则退出运行*/
　　　　 printf("存储空间分配失败！ ");
　　　　 exit(1);
　　 }
　　 L->list=p;　　/*使list指向新线性表空间*/
　　 L->maxSize=2*L->maxSize;　　/*把线性表空间大小修改为新的长度*/
}
/*1.初始化线性表L，即进行动态存储空间分配并置L为一个空表*/
voidinitList(structList*L,intms)
{
　　 /*检查ms是否有效，若无效的则退出运行*/
　　 if(ms<=0){
　　　　 printf("MaxSize非法！ ");
　　　　 exit(1);　　/*执行此函数中止程序运行，此函数在stdlib.h中有定义*/
　　 }
　　 L->maxSize=ms;　　/*设置线性表空间大小为ms*/
　　 L->size=0;
　　 L->list=malloc(ms*sizeof(elemType));
　　 if(!L->list){
　　　　 printf("空间分配失败！ ");
　　　　 exit(1);
　　 }
　　 return;
}
/*2.清除线性表L中的所有元素，释放存储空间，使之成为一个空表*/
voidclearList(structList*L)
{
　　 if(L->list!=NULL){
　　　　 free(L->list);
　　　　 L->list=0;
　　　　 L->size=L->maxSize=0;
　　 }
　　 return;
}
/*3.返回线性表L当前的长度，若L为空则返回０*/
intsizeList(structList*L)
{
　　 returnL->size;
}
/*4.判断线性表L是否为空，若为空则返回1,否则返回0*/
intemptyList(structList*L)
{
　　 if(L->size==0){
　　　　 return1;
　　 }
　　 else{
　　　　 return0;
　　 }
}
/*5.返回线性表L中第pos个元素的值，若pos超出范围，则停止程序运行*/
elemTypegetElem(structList*L,intpos)
{
　　 if(pos<1||pos>L->size){　　/*若pos越界则退出运行*/
　　　　 printf("元素序号越界！ ");
　　　　 exit(1);
　　 }
　　 returnL->list[pos-1];　　/*返回线性表中序号为pos值的元素值*/
}
/*6.顺序扫描（即遍历）输出线性表L中的每个元素*/
voidtraverseList(structList*L)
{
　　 inti;
　　 for(i=0;i<L->size;i++){
　　　　 printf("%d",L->list[i]);
　　 }
　　 printf(" ");
　　 return;
}
/*7.从线性表L中查找值与x相等的元素，若查找成功则返回其位置，否则返回-1*/
intfindList(structList*L,elemTypex)
{
　　 inti;
　　 for(i=0;i<L->size;i++){
　　　　 if(L->list[i]==x){
　　　　　　 returni;
　　　　 }
　　 }
　　 return-1;
}
/*8.把线性表L中第pos个元素的值修改为x的值，若修改成功返回1，否则返回0*/
intupdatePosList(structList*L,intpos,elemTypex)
{
　　 if(pos<1||pos>L->size){　　/*若pos越界则修改失败*/
　　　　 return0;
　　 }
　　 L->list[pos-1]=x;
　　 return1;
}
/*9.向线性表L的表头插入元素x*/
voidinserFirstList(structList*L,elemTypex)
{
　　 inti;
　　 if(L->size==L->maxSize){
　　　　 againMalloc(L);
　　 }
　　 for(i=L->size-1;i>=0;i--){
　　　　 L->list[i+1]=L->list[i];
　　 }
　　 L->list[0]=x;
　　 L->size++;
　　 return;
}
/*10.向线性表L的表尾插入元素x*/
voidinsertLastList(structList*L,elemTypex)
{
　　 if(L->size==L->maxSize){　　/*重新分配更大的存储空间*/
　　　　 againMalloc(L);
　　 }
　　 L->list[L->size]=x;　　/*把x插入到表尾*/
　　 L->size++;　　/*线性表的长度增加１*/
　　 return;
}
/*11.向线性表L中第pos个元素位置插入元素x，若插入成功返回１，否则返回０*/
intinsertPosList(structList*L,intpos,elemTypex)
{
　　 inti;
　　 if(pos<1||pos>L->size+1){　　/*若pos越界则插入失败*/
　　　　 return0;
　　 }
　　 if(L->size==L->maxSize){　　/*重新分配更大的存储空间*/
　　　　 againMalloc(L);
　　 }
　　 for(i=L->size-1;i>=pos-1;i--){
　　　　 L->list[i+1]=L->list[i];
　　 }
　　 L->list[pos-1]=x;
　　 L->size++;
　　 return1;
}
/*12.向有序线性表L中插入元素x,　使得插入后仍然有序*/
voidinsertOrderList(structList*L,elemTypex)
{
　　 inti,j;
　　 /*若数组空间用完则重新分配更大的存储空间*/
　　 if(L->size==L->maxSize){
　　　　 againMalloc(L);
　　 }
　　 /*顺序查找出x的插入位置*/
　　 for(i=0;i<L->size;i++){
　　　　 if(x<L->list[i]){
　　　　　　 break;
　　　　 }
　　 }
　　 /*从表尾到下标i元素依次后移一个位置，把i的位置空出来*/
　　 for(j=L->size-1;j>=i;j--)
　　　　 L->list[j+1]=L->list[j];
　　 /*把x值赋给下标为i的元素*/　　
　　 L->list[i]=x;
　　 /*线性表长度增加1*/
　　 L->size++;
　　 return;
}
/*13.从线性表L中删除表头元素并返回它，若删除失败则停止程序运行*/
elemTypedeleteFirstList(structList*L)
{
　　 elemTypetemp;
　　 inti;
　　 if(L->size==0){
　　　　 printf("线性表为空，不能进行删除操作！ ");
　　　　 exit(1);
　　 }
　　 temp=L->list[0];
　　 for(i=1;i<L->size;i++)
　　　　 L->list[i-1]=L->list[i];
　　 L->size--;
　　 returntemp;
}
/*14.从线性表L中删除表尾元素并返回它，若删除失败则停止程序运行*/
elemTypedeleteLastList(structList*L)
{
　　 if(L->size==0){
　　　　 printf("线性表为空，不能进行删除操作！ ");
　　　　 exit(1);
　　 }
　　 L->size--;
　　 returnL->list[L->size];　　　　/*返回原来表尾元素的值*/
}
/*15.从线性表L中删除第pos个元素并返回它，若删除失败则停止程序运行*/
elemTypedeletePosList(structList*L,intpos)
{
　　 elemTypetemp;
　　 inti;
　　 if(pos<1||pos>L->size){　　　　/*pos越界则删除失败*/
　　　　 printf("pos值越界，不能进行删除操作！ ");
　　　　 exit(1);
　　 }
　　 temp=L->list[pos-1];
　　 for(i=pos;i<L->size;i++)
　　　　 L->list[i-1]=L->list[i];
　　 L->size--;
　　 returntemp;
}
/*16.从线性表L中删除值为x的第一个元素，若成功返回1，失败返回0*/
intdeleteValueList(structList*L,elemTypex)
{
　　 inti,j;
　　 /*从线性表中顺序查找出值为x的第一个元素*/
　　 for(i=0;i<L->size;i++){
　　　　 if(L->list[i]==x){　　
　　　　　　 break;
　　　　 }
　　 }
　　 /*若查找失败，表明不存在值为x的元素，返回0*/
　　 if(i==L->size){
　　　　 return0;
　　 }
　　 /*删除值为x的元素L->list[i]*/
　　 for(j=i+1;j<L->size;j++){
　　　　 L->list[j-1]=L->list[j];
　　 }
　　 L->size--;
　　 return1;
}
/************************************************************************/
voidmain()
{
　　 inta[10]={2,4,6,8,10,12,14,16,18,20};
　　 inti;
　　 structListL;
　　 initList(&L,5);
　　 for(i=0;i<10;i++){
　　　　 insertLastList(&L,a[i]);
　　 }
　　 insertPosList(&L,11,48);　　　　insertPosList(&L,1,64);
　　 printf("%d ",getElem(&L,1));
　　 traverseList(&L);
　　 printf("%d ",findList(&L,10));
　　 updatePosList(&L,3,20);
　　 printf("%d ",getElem(&L,3));
　　 traverseList(&L);
　　 deleteFirstList(&L);　　　　　　deleteFirstList(&L);
　　 deleteLastList(&L);　　　　　　　　deleteLastList(&L);
　　 deletePosList(&L,5);　　　　　　;deletePosList(&L,7);
　　 printf("%d ",sizeList(&L));
　　 printf("%d ",emptyList(&L));
　　 traverseList(&L);
　　 clearList(&L);
　　 return0;
}#include<stdio.h>
#include<stdlib.h>
#defineNN12
#defineMM20
typedefintelemType;
/************************************************************************/
/*　　　　　　以下是关于线性表链接存储（单链表）操作的16种算法　　　　*/
/************************************************************************/
structsNode{　　/*定义单链表结点类型*/
　　 elemTypedata;
　　 structsNode*next;
};
/*1.初始化线性表，即置单链表的表头指针为空*/
voidinitList(structsNode**hl)
{
　　 *hl=NULL;
　　 return;
}
/*2.清除线性表L中的所有元素，即释放单链表L中所有的结点，使之成为一个空表*/
voidclearList(structsNode**hl)
{
　　 /*cp和np分别作为指向两个相邻结点的指针*/
　　 structsNode*cp,*np;
　　 cp=*hl;
　　 /*遍历单链表，依次释放每个结点*/
　　 while(cp!=NULL){
　　　　 np=cp->next;　　/*保存下一个结点的指针*/
　　　　 free(cp);
　　　　 cp=np;
　　 }
　　 *hl=NULL;　　　　/*置单链表的表头指针为空*/
　　 return;
}
/*3.返回单链表的长度*/
intsizeList(structsNode*hl)
{
　　 intcount=0;　　　　/*用于统计结点的个数*/
　　 while(hl!=NULL){
　　　　 count++;
　　　　 hl=hl->next;
　　 }
　　 returncount;
}
/*4.检查单链表是否为空，若为空则返回１，否则返回０*/
intemptyList(structsNode*hl)
{
　　 if(hl==NULL){
　　　　 return1;
　　 }else{
　　　　 return0;
　　 }
}
/*5.返回单链表中第pos个结点中的元素，若pos超出范围，则停止程序运行*/
elemTypegetElem(structsNode*hl,intpos)
{
　　 inti=0;　　　　/*统计已遍历的结点个数*/
　　 if(pos<1){
　　　　 printf("pos值非法，退出运行！ ");
　　　　 exit(1);
　　 }
　　 while(hl!=NULL){
　　　　 i++;
　　　　 if(i==pos){
　　　　　　 break;
　　　　 }
　　　　 hl=hl->next;
　　 }
　　 if(hl!=NULL){
　　　　 returnhl->data;
　　 }else{
　　　　 printf("pos值非法，退出运行！ ");
　　　　 exit(1);
　　 }
}
/*6.遍历一个单链表*/
voidtraverseList(structsNode*hl)
{
　　 while(hl!=NULL){
　　　　 printf("%5d",hl->data);
　　　　 hl=hl->next;
　　 }
　　 printf(" ");
　　 return;
}
/*7.从单链表中查找具有给定值x的第一个元素，若查找成功则返回该结点data域的存储地址，否则返回NULL*/
elemType*findList(structsNode*hl,elemTypex)
{
　　 while(hl!=NULL){
　　　　 if(hl->data==x){
　　　　　　 return&hl->data;
　　　　 }else{
　　　　　　 hl=hl->next;　　
　　　　 }
　　 }
　　 returnNULL;
}
/*8.把单链表中第pos个结点的值修改为x的值，若修改成功返回１，否则返回０*/
intupdatePosList(structsNode*hl,intpos,elemTypex)
{
　　 inti=0;
　　 structsNode*p=hl;
　　 while(p!=NULL){　　　　/*查找第pos个结点*/
　　　　 i++;
　　　　 if(pos==i){
　　　　　　 break;
　　　　 }else{
　　　　　　 p=p->next;
　　　　 }
　　 }
　　 if(pos==i){
　　　　 p->data=x;
　　　　 return1;
　　 }else{
　　　　 return0;
　　 }
}
/*9.向单链表的表头插入一个元素*/
voidinsertFirstList(structsNode**hl,elemTypex)
{
　　 structsNode*newP;
　　 newP=malloc(sizeof(structsNode));
　　 if(newP==NULL){
　　　　 printf("内存分配失败，退出运行！ ");
　　　　 exit(1);
　　 }
　　 newP->data=x;　　　　/*把x的值赋给新结点的data域*/
　　 /*把新结点作为新的表头结点插入*/
　　 newP->next=*hl;　　　　
　　 *hl=newP;
　　 return;
}
/*10.向单链表的末尾添加一个元素*/
voidinsertLastList(structsNode**hl,elemTypex)
{
　　 structsNode*newP;
　　 newP=malloc(sizeof(structsNode));
　　 if(newP==NULL){
　　　　 printf("内在分配失败，退出运行！ ");
　　　　 exit(1);
　　 }
　　 /*把x的值赋给新结点的data域，把空值赋给新结点的next域*/
　　 newP->data=x;
　　 newP->next=NULL;
　　 /*若原表为空，则作为表头结点插入*/
　　 if(*hl==NULL){
　　　　 *hl=newP;　　　　
　　 }
　　 /*查找到表尾结点并完成插入*/
　　 else{
　　　　 structsNode*p=NULL;
　　　　 while(p->next!=NULL){
　　　　　　 p=p->next;
　　　　 }
　　　　 p->next=newP;
　　 }
　　 return;
}
/*11.向单链表中第pos个结点位置插入元素为x的结点，若插入成功返回１，否则返回０*/
intinsetPosList(structsNode**hl,intpos,elemTypex){
　　 inti=0;
　　 structsNode*newP;
　　 structsNode*cp=*hl,*ap=NULL;
　　 /*对pos值小于等于０的情况进行处理*/
　　 if(pos<=0){
　　　　 printf("pos值非法，返回０表示插入失败！ ");
　　　　 return0;
　　 }
　　 /*查找第pos个结点*/
　　 while(cp!=NULL){
　　　　 i++;
　　　　 if(pos==i){
　　　　　　 break;
　　　　 }else{
　　　　　　 ap=cp;
　　　　　　 cp=cp->next;
　　　　 }
　　 }
　　 /*产生新结点，若分配失败，则停止插入*/
　　 newP=malloc(sizeof(structsNode));
　　 if(newP==NULL){
　　　　 printf("内存分配失败，无法进行插入操作！ ");
　　　　 return0;
　　 }
　　 /*把x的值赋给新结点的data域*/
　　 newP->data=x;
　　 /*把新结点插入到表头*/
　　 if(ap==NULL){
　　　　 newP->next=cp;　　　　/*或改为newP->next=*hl;*/
　　　　 *hl=newP;
　　 }
　　 /*把新结点插入到ap和cp之间*/
　　 else{
　　　　 newP->next=cp;
　　　　 ap->next=newP;
　　 }
　　 return1;　　　　/*插入成功返回1*/
}
/*12.向有序单链表中插入元素x结点，使得插入后仍然有序*/
voidinsertOrderList(structsNode**hl,elemTypex)
{
　　 /*把单链表的表头指针赋给cp，把ap置空*/
　　 structsNode*cp=*hl,*ap=NULL;
　　 /*建立新结点*/
　　 structsNode*newP;
　　 newP=malloc(sizeof(structsNode));
　　 if(newP==NULL){
　　　　 printf("内在分配失败，退出运行！ ");
　　　　 exit(1);
　　 }
　　 newP->data=x;　　　　/*把x的值赋给新结点的data域*/
　　 /*把新结点插入到表头*/
　　 if((cp==NULL)||(x<cp->data)){
　　　　 newP->next=cp;
　　　　 *hl=newP;
　　　　 return;
　　 }
　　 /*顺序查找出x结点的插入位置*/
　　 while(cp!=NULL){
　　　　 if(x<cp->data){
　　　　　　 break;
　　　　 }else{
　　　　　　 ap=cp;
　　　　　　 cp=cp->next;
　　　　 }
　　 }
　　 /*把x结点插入到ap和cp之间*/
　　 newP->next=cp;
　　 ap->next=newP;
　　 return;
}
/*13.从单链表中删除表头结点，并把该结点的值返回，若删除失败则停止程序运行*/
elemTypedeleteFirstList(structsNode**hl)
{
　　 elemTypetemp;
　　 structsNode*p=*hl;　　　　/*暂存表头结点指针，以便回收*/
　　 if(*hl==NULL){
　　　　 printf("单链表为空，无表头可进行删除，退出运行！ ");
　　　　 exit(1);
　　 }
　　 *hl=(*hl)->next;　　　　/*使表头指针指向第二个结点*/
　　 temp=p->data;　　　　　　/*暂存原表头元素，以便返回*/
　　 free(p);　　　　　　　　/*回收被删除的表头结点*/
　　 returntemp;　　　　　　/*返回第一个结点的值*/
}
/*14.从单链表中删除表尾结点并返回它的值，若删除失败则停止程序运行*/
elemTypedeleteLastList(structsNode**hl)
{
　　 elemTypetemp;
　　 /*初始化cp和ap指针，使cp指向表头结点，使ap为空*/
　　 structsNode*cp=*hl;
　　 structsNode*ap=NULL;
　　 /*单链表为空则停止运行*/
　　 if(cp==NULL){
　　　　 printf("单链表为空，无表头进行删除，退出运行！ ");
　　　　 exit(1);
　　 }
　　 /*从单链表中查找表尾结点，循环结束时cp指向表尾结点，ap指向其前驱结点*/
　　 while(cp->next!=NULL){
　　　　 ap=cp;
　　　　 cp=cp->next;
　　 }
　　 /*若单链表中只有一个结点，则需要修改表头指针*/
　　 if(ap==NULL){
　　　　 *hl=(*hl)->next;　　　　/*或改为*hl=NULL;*/
　　 }
　　 /*删除表尾结点*/
　　 else{
　　　　 ap->next=NULL;
　　 }
　　 /*暂存表尾元素，以便返回*/
　　 temp=cp->data;
　　 free(cp);　　　　/*回收被删除的表尾结点*/
　　 returntemp;　　　　/*返回表尾结点的值*/
}
/*15.从单链表中删除第pos个结点并返回它的值，若删除失败则停止程序运行*/
elemTypedeletePosList(structsNode**hl,intpos)
{
　　 inti=0;
　　 elemTypetemp;
　　 /*初始化cp和ap指针，使cp指向表头结点，使ap为空*/
　　 structsNode*cp=*hl;
　　 structsNode*ap=NULL;
　　 /*单链表为空或pos值非法则停止运行 http://bianceng.cn（编程入门）*/
　　 if((cp==NULL)||(pos<=0)){
　　　　 printf("单链表为空或pos值不正确，退出运行！ ");
　　　　 exit(1);
　　 }
　　 /*从单链表中查找第pos个结点，找到后由cp指向该结点，由ap指向其前驱结点*/
　　 while(cp!=NULL){
　　　　 i++;
　　　　 if(i==pos){
　　　　　　 break;
　　　　 }
　　　　 ap=cp;
　　　　 cp=cp->next;
　　 }
　　 /*单链表中没有第pos个结点*/
　　 if(cp==NULL){
　　　　 printf("pos值不正确，退出运行！ ");
　　　　 exit(1);
　　 }
　　 /*若pos等于1，则需要删除表头结点*/
　　 if(pos==1){
　　　　 *hl=(*hl)->next;　　　　/*或改为*hl=cp->next;*/
　　 }
　　 /*否则删除非表头结点，此时cp指向该结点，ap指向前驱结点*/
　　 else{
　　　　 ap->next=cp->next;
　　 }
　　 /*暂存第pos个结点的值，以便返回*/
　　 temp=cp->data;
　　 free(cp);　　　　/*回收被删除的第pos个结点*/
　　 returntemp;　　/*返回在temp中暂存的第pos个结点的值*/
}
/*16.从单链表中删除值为x的第一个结点，若删除成功则返回1,否则返回0*/
intdeleteValueList(structsNode**hl,elemTypex)
{
　　 /*初始化cp和ap指针，使cp指向表头结点，使ap为空*/
　　 structsNode*cp=*hl;
　　 structsNode*ap=NULL;
　　 /*从单链表中查找值为x的结点，找到后由cp指向该结点，由ap指向其前驱结点*/
　　 while(cp!=NULL){
　　　　 if(cp->data==x){
　　　　　　 break;
　　　　 }
　　　　 ap=cp;
　　　　 cp=cp->next;
　　 }
　　 /*若查找失败，即该单链表中不存在值为x的结点，则返回0*/
　　 if(cp==NULL){
　　　　 return0;
　　 }
　　 /*如果删除的是表头或非表头结点则分别进行处理*/
　　 if(ap==NULL){
　　　　 *hl=(*hl)->next;　　　　/*或改为*hl=cp->next*/
　　 }else{
　　　　 ap->next=cp->next;
　　 }
　　 free(cp);　　　　/*回收被删除的结点*/
　　 return1;　　　　/*返回1表示删除成功*/
}
/************************************************************************/
intmain(intargc,char*argv[])
{
　　 inta[NN];
　　 inti;
　　 structsNode*p,*h,*s;
　　 srand(time(NULL));
　　 initList(&p);
　　 for(i=0;i<NN;i++){
　　　　 a[i]=rand()&MM;
　　 }
　　 printf("随机数序列：");
　　 for(i=0;i<NN;i++){
　　　　 printf("%5d",a[i]);
　　 }
　　 printf(" ");
　　 printf("随机数逆序：");
　　 for(i=0;i<NN;i++){
　　　　 insertFirstList(&p,a[i]);
　　 }
　　 traverseList(p);
　　 printf("单链表长度：%5d ",sizeList(p));
　　 for(h=p;h!=NULL;h=h->next){
　　　　 while(deleteValueList(&(h->next),h->data)){
　　　　　　 ;
　　　　 }
　　 }
　　 printf("去除重复数：");
　　 traverseList(p);
　　 printf("单链表长度：%5d ",sizeList(p));
　　 h=NULL;
　　 for(s=p;s!=NULL;s=s->next){
　　　　 insertOrderList(&h,s->data);
　　 }
　　 printf("有序表序列：");
　　 traverseList(h);
　　 clearList(&p);
　　 system("pause");
　　 return0;
}