数据结构C语言实现之线性表
2007-10-24 11:57:01 来源：WEB开发网#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;
}
中查找“数据结构C语言实现之线性表”更多相关内容
中查找“数据结构C语言实现之线性表”更多相关内容更多精彩
赞助商链接
