常见的线性表的基本运算

常见的线性表的基本运算：InitList(&L)构造一个空的线性表L,即表的初始化。DestroyList(&L)销毁线性表。ClearList(&L)将L重置为空表。ListEmpty(L)若L为空表，则返回TRUE,否则返回FALSE。ListLength(L)求线性表L中的结点个数，即求表长。GetElem(L,i,&e)用e返回L中第i数据个元素的值。这里要求l<i<ListLength(L)LocateElem(L.pare())返回L中第1个与e满足关系compare()的数据元素的位序。不存在，则返回值为0。ListInsert(&L,i>e)在L中第i个位置之前插入新的数据元素e,L的长度加1。ListDelete(&L,i,&e)删除L的第i个数据元素，并用e返回其值，L的长度减1。组合基本运算，实现复杂运算：.假设利用两个线性表LA和LB分别表示两个集合A和B(即：线性表中的数据元素即为集合中的成员)，现要求一个新的集合A=AUB"［思想］:这就要求对线性表作如下操作：扩大线性表LA,将存在于线性表LB中而不存在于线性表LA中的数据元素插入到线性表LA中去。只要从线性表LB中依次取得每个数据元素，并依值在线性表LA中进行查访，若不存在，则插入之。［算法描述如下］:voidunion(List&La,ListLb){〃将所有在线性表Lb中但不在La中的数据元素插入到La中；La_len=ListLength(La)：Lb_len=ListLength(Lb)；〃求线性表的长度for(i=1；i<=Lb_len；i++){GetElem(Lb,i,e)：〃取Lb中第i个数据元素赋给eif(!LocateElem(La.e，equal))Listinsert(La,++Lalen,e)；//La中不存在和e相同的数据元素，则插入)}//union算法2.1.已知线性表LA和LB中的数据元素按值非递减有序排列，现要求将LA和LB归并为•个新的线性表LC,且LC中的数据元素仍按值非递减有序排列。［思想］:从上述问题要求可知，LC中的数据元素或是LA中的数据元素，或是LB中的数据元素，则只

要先设LC为空表，然后将LA或LB中的元素逐个插入到LC中即可。为使LC中元素按值非递减有序排列，可设两个指针i和j分别指向LA和LB中某个元素，若设i当前所指的元素为a,j当前所指的元素为b,则当前应插入到LC中的元素min(a,b)；显然，指针i和j的初值均为1,在所指元素插入LC之后，在LA或LB中顺序后移。［归并算法如算法2.2所示］:VoidMergeList(ListLa,ListLb,List&Lc){〃已知线性表La和Lb中数据元素按值非递减排列。归并La和Lb得到新的线性表Lc,Lc的数据元素也按值非递减排列InitList(Lc)；i=j=1；k=0；Lalen=ListLength(La)；Lbjen=ListLehgth(Lb)；while((i<=La_len)&&(j<=Lb_len))//La和Lb均非空{GetElem(La,i,ai)；GetElem(Lb,j,bj)：if(ai<=bj){Listlnsert(Lc>++k»ai)；++i；}else{Listlnsert(Lc,-H-k»bj)；-Hj：}}while(i<=La_len){GetElem(La,i++,ai)；JIII+一^-»lli-Mli~1l-k~Listlnsert(Lc»++k,ai)：}while(j<=Lb_len){GetElem(Lb,j++,bj)；Listlnsert(Lc,-H-k,bj)；)}//算法JIII+一^-»lli-Mli~1l-k~voidMcrgcListL(LinkList&La»LinkList&Lb,LinkList&Lc){〃已知单链线性表La和Lb的元素按值非递减排列。归并La和Lb得到新的单链线性表Lc,Lc元素也按值非递减排列。pa=La—>next；pb=Lb->next；Lc=pc=La；〃用La的头结点作为Lc的头结点while(pa&&pb){if(pa—>data<pb—>data){pc—>next=pa；pc=pa；pa=pa—>next：}else{pc—>next=pb；pc=pb；pb=pb—>next}}pc一>next=pa?pa:pb//插入剩余段free(Lb)；〃释放Lb的头结点}//MerqeList_L算法2.122.在带头结点的双链循环线性表中第i个位置之前插入元素e。StatusListlnsertDuL(DuLinkList&L,inti,ElemTypee){〃在带头结点的双链循环线性表中第i个位置之前插入元素e,i的合法值为1<=i<=表长+1.if(!(p=GetElemP_DuL(L,i)))〃在L中确定第i个元素的位置指针preturnERROR;//p=NULL,即第i个元素不存在if(!(s=(DuLinkList)malloc(sizeof(DuLNode)))returnERROR;s->data=e;s->prior=p->prior;p->prior->next=s;s->next=p;p->prior=s;returnOK;}//ListInsert_DuL;算法2.186.删除带头结点的双链循环线性表L的第i个元素。StatusListDclctc_DuL(DuLinkList&L,inti,ElemType&e)(〃删除带头结点的双链循环线性表L的第i个元素，i的合法值为氏/表长i«!(p=GetElcmP_DuL(L,i)))〃在L中确定第i个元素的位置指针preturnERROR：//p=NULL,即第i个元素不存在e=p->data；p—>prior—>next=p->next;p—>next—>prior=p—>prior;free(p)；returnOK}//ListDelctcDuL定点起始远动圆设计程序要求:设计一个运动的圆.起点由用户输入！include"graphics.h"include"stdlib.h"include"stdio.h"include"dos.h"intmain。

inti,gd=DETECT,gr;registerbgidriver(EGAVGAdriver);initgraph(&gd,&gr,"c:\\turboc2");cleardevice();for(i=0;i<300;i+=10)(cleardevice();circle(50+i,50+i,20);delay(100);/*延迟100毫秒*/)getch();closegraph();hi贴吧新浪微博腾讯微博QQ空间人人网豆瓣MSN1回答时间：2008-1-2220:14我来评论实验目的和要求：编写一个简单的算法解决一个具体的问题并在C环境中上机实现。对己学的C语言设计知识作一回顾。实验内容：用C语言编程求解百鸡问题。(两种方法)编程求解100~1000之间的所有素数。用基本穷举法用筛法实验二几种算法比较 用C语言编程求解百鸡问题1¥#include<stdio.h>voidmain(){intcock,hen;for(cock=0;cock<=20;cock++)for(hen=0;hen<=100/3;hen++)if(cock*5+hen*3+(100-cock-hen)*1<=100)printf("cock:%d,hen:%d,chick:%d\n",cock,hen,100-cock-hen);

}#include<stdio.h>voidchicken_question(intchicken_num,int*k,intg[],intm[],intx[])inta,b,c,t;t=0;for(a=0;a<=chicken_num/5;a++)for(b=0;b<=chicken_num/3;b++)c=100-a-b;if((a+b+c)==chicken_num&&(5*a+3*b+c/3==chicken_num)&&(c%3==0))g[t]=a;m[t]=b;x[t]=c;t++；)}*k=t;}2¥main()intn;intgongji[50],muji[50],xiaoji[50],num=0;inti,*p_num=#printfF公鸡5元每只，母鸡3元每只，小鸡3只1元)printf("n元买n只鸡,请输入n的值：")；scanf("%d",&n);chicken_question(n,p_num,gongji,muji,xiaoji);for(i=0;i<num;i++)-{printf("%d%d%d",gongji[i],muji[i],xiaoji[i]);})3¥voidmain(){intx,y,z,j=0;printf(MFolleingarepossibleplanstobuy100fowlswith100Yuan.Wn1');for(x=0;x<=20;x++)for(y=0;y<=33;y++) z=100-x-y;if(z%3==0&&5*x+3*y+z/3==100) printf(M%2d:cock=%2dhen=%2dchicken=%2d\\n”,++j,x,y,z);}*运行结果

Follwingarepossibleplanstobuy100fowlswith100Yuan.1:cock=0hen=25chicken=752:cock=4hen=18chicken=783:cock=8hen=11chicken=814:cock=12hen=4chicken=84编程求解100~1000之间的所有素数。#include<iostream.h>#include<math.h>boolisPrime(intn)(ints,i;〃cout<<"请输入一个大于二的正整数："；//cin»n;s=(int)sqrt(n);for(i=2;i<=s;i++)if(n%i==O)returnfalse;returntrue;〃cout<<"该数是素数!//else coutvv"概数不是素数！";}voidmain()(intm;for(m=100;m<=999;m++)if(isPrime(m))cout«m«"\t";)Q****实验目的和要求：(1)学习工程中常用的几种算法设计方法(2)通过上机实践来比较这几种算法之间的区别和联系实验内容：输出自然数「n。分别用for循环和递归算法实现。求n!。分别用for循环和递归算法实现。用二分法求解方程的根，方程式为f(x)=x'-5x2+16x-80。使用减半递推方法完成。

实验三线性表的初始化、插入运算实验目的和要求：(1)学习线性表的顺序存储结构(2)学会建立线性表(3)学会线性表顺序存储结构下的插入运算实验内容：初始化一个空的线性表，并输入指定元素，然后输出。实验用例：D={13,29,5,7,81,23,92,36,24,10)在第•题的基础上自定义一个函数insert,该函数用来实现在指定的元素前插入给定的元素(例如：在81前插入101)o注意上溢的发生。试写出在顺序存储结构下逆转线性表的算法。(可选)提示：新建一个线性表，从原表按相反顺序复制。实验四线性表的删除运算实验目的和要求：(1)掌握线性表中顺序表的结构(2)学会线性表顺序存储结构下的删除运算实验内容：在实验三的源程序中增加一个函数dellist(),用来实现顺序存储结构下线性表的删除算法(例如：删除指定元素81)o实验用例：D={13,29,5,7,81,23,92,36,24,10}用菜单实现在源程序中调用线性表删除算法的功能。实验五线性单链表的初始化、插入算法实验目的和要求：(1)学会建立单链表

(2)学会在单链表中实现数据的插入实验内容：用C语言编程，建立一个单链表。要求完成，初始化函数的编写、输入函数的编写、输出函数的编写、插入指定元素函数的编写。实验六线性单链表的删除运算实验目的和要求：(1)掌握线性单链表的结构(2)学会在单链表中实现数据的删除实验内容：1.在实验五的基础上，增加一个自定义函数del(),该函数实现在一个单链表中删除指定的元素。2.在主函数中编写菜单，实现插入元素和删除元素的调用。#include<iostream>usingnamespacestd;template<classT>classlist;template<classT>classnode(friendlist<T>;private:Tdata;node<T>*next;public:node<T>():data(0),next(NULL){);~node<T>(){}TgetData(){returndata;}node<T>*getNext(){returnnext;}}；

template<classT>classlist(private:node<T>*head;public:list(){head=newnode<T>;}intinsert(T&);intremove(T&);node<T>*find(T&);voidprint();voidsort();}；template<classT>intlist<T>::insert(T&x){node<T>*p=newnode<T>;p->data=x;if(!p)return0;p->next=head->next;head->next=p;return1;template<classT>intlist<T>::remove(T&x){node<T>*p=find(x);if(!p)return0;node<T>*q=p->next;p->next=q->next;deleteq;return1;}template<classT>node<T>*list<T>::find(T&x)node<T>*q=head;

while(q->next!=NULL)if(q->next->data==x)returnq;q=q->next;}returnNULL;)template<classT>voidlist<T>::sort()(node<T>*p=head->next,*q;for(;p!=NULL;p=p->next)for(q=p->next;q!=NULL;q=q->next)if(p->data>q->data)(Ttemp=q->data;q->data=p->data;p->data=temp;}}template<classT>voidlist<T>::print()(node<T>*q=head->next;while(q!=NULL)(cout«q->data;q=q->next;)cout«endl;)template<classT>list<T>::~list()(node<T>*p=head->next;while(p!=NULL)(head->next=p->next;deletep;p=head->next;

deletehead;)intmain()(list<int>I;intx;do(cin»x;//input0exitif(x==O)break;l.insert(x);}while(1);l.sort();l-printO;cin»x;node<int>*p=Lfind(x)->getNext();cout«p->getData()«endl;l.remove(x);l-printO;return0;实现双链表各种基本运算的算法include<stdio.h>/*定/*指向前/*定/*指向前elemtypedata;structdnode*prior;

驱结点*/structdnode*next;继结点*/}dlinklist;voidinitlist(dlinklist*&L){L=(dlinklist)malloc(sizeof(dlinklist));点*/L->prior=L->next=NULL;)voiddestroylist(dlinklist*&L){dlinklist*p=L,*q=p-〉next;while(q!=NULL){free(p);/*指向后/*创建头结P/*指向后/*创建头结q=p->next;free(p);intlistempty(dlinklist*L){return(L->next==NULL);)intlistlength(dlinklist*L){dlinklist*p=L;inti=0;while(p->next!=NULL){i++;p=p->next;)return(i);)voiddisplist(dlinklist*L)(dlinklist*p=L-〉next;while(p!=NULL)printf(〃%c〃,p->data);p=p->next;)printf(〃\n〃);)intgetelem(dlinklist*L,inti,elemtype&e){intj=0;dlinklist*p=L;while(j<i&&p!=NULL){j++；p=p->next;)if(p==NULL)return0;else{e=p->data;return1;intlocateelem(dlinklist*L,elemtypee)dlinklist*p=L->next;intn=l;while(p!=NULL&&p->data!=e){p=p->next;n++;)if(p==NULL)return(0);elsereturn(n);)intlistinsert(dlinklist*&L,inti,elemtypee){intj=0;dlinklist*p=L,*s;while(j<i-l&&p!=NULL){j++；p=p->next;if(p==NULL) /*未找到第IT个结点*/return0;else /*找到第IT个结点*/{s=(dlinklist*)malloc(sizeof(dlinklist));/*创建新结点*s*/s->data=e;s->next=p->next; /*将*s插到*p之后*/if(p->next!=NULL)p->next->prior=s;s->prior=p;p->next=s;return1;))intlistdelete(dlinklist*&L,inti,elemtype&e){intj=0;dlinklist*p=L,*q;

while(j<i-l&&p!=NULL)j++；p=p->next;)if(p—NULL)到第iT个结点*/return0;else1-1个结点*/{q=p->next;要删除的结点*/if(q==NULL)return0;T个结点*/p->next=q->next;表中删除*q结点*/if(p->next!=NULL)p->next->prior=p;free(q);/*未找/*/*未找/*找到第/*q指向/*不存在第/*从单链/*释放*q结点voidmain()dlinklist*h;elemtypee;printf(〃(1)初始化单链表