数据结构源代码归纳(一)
2008年08月01日 星期五 23:46 第一章 绪论 P8
例： 计算f=1！+2！+3！+…+n！，用C语言描述。 void factorsum（n） int n； {
int i，j； int f，w； f=0；
for （i=1；i〈=n；i++） {
w=1；
for （j=1；j〈=i；j++） w=w*j； f=f+w； }
return； }
第二章 线性表
P16【算法2.1 顺序表的插入】
int Insert(Elemtype List[],int *num,int i,Elemtype x)
{/*在顺序表List[]中，*num为表尾元素下标位置，在第i个元素前插入数据元素x，若成功，返回TRUE，否则返回FALSE。*/ int j;
if (i<0||i>*num+1)
{printf(\ /*插入位置出错*/ return FALSE;}
if (*num>=MAXNUM-1) {printf(\
return FALSE;} /*表已满*/ for (j=*num;j>=i;j--)
List[j+1]=List[j]; /*数据元素后移*/ List[i]=x; /*插入x*/ (*num)++; /*长度加1*/ return TRUE;}
P18【算法2.2 顺序表的删除】
int Delete(Elemtype List[],int *num,int i)
{/*在线性表List[]中，*num为表尾元素下标位置，删除第i个长度，线性表的长度减1，若成功，则返回TRUE；否则返回FALSE。*/
int j;
if(i<0||i>*num)
{printf(\删除位置出错！*/ for(j=i+1;j<=*num;j++)
List[j-1]=List[j]; /*数据元素前移*/ (*num)--; /*长度减1*/ return TRUE; }
P19 例：将有序线性表La={2,4,6,7,9}，Lb={1,5,7,8}，合并为Lc={1,2,4,5,6,7,7,8,9}。
void merge(Elemtype La[],Elemtype Lb[],Elemtype **Lc) { int i,j,k;
int La_length,Lb_length; i=j=0;k=0;
La_length=Length(La);Lb_length=Length(Lb); /*取表La,Lb的长度*/ Initiate(Lc); /*初始化表Lc*/ While (i<=La_length&&j<=Lb_length) { a=get(La,i);b=get(Lb,j);
if(a } /*将La和Lb的元素插入到Lc中*/ while (i<=La_length) { a=get(La,i);insert(Lc,++k,a);} while (j<=lb_length) { b=get(La,j);insert(Lc,++k,b); } } P21例如：下面定义的结点类型中，数据域包含三个数据项：学号、姓名、成绩。 Struct student { char num[8]; /*数据域*/ har name[8]; /*数据域*/ int score; /*数据域*/ struct student *next; /*指针域*/ } P21单链表结点结构定义为： Typedef struct slnode { Elemtype data; struct slnode *next; }slnodetype; slnodetype *p,*q,*s; P21 【算法2.3 单链表的初始化】 int Initiate(slnodetype * *h) { if((*h=(slnodetype*)malloc(sizeof(slnodetype)))==NULL) return FALSE; (*h)->next=NULL; return TRUE; } P22 【算法2.4 单链表的后插入】 { s=(slnodetype*)malloc(sizeof(slnodetype)); s->data=x; s->next=p->next;p->next=s;} P22 【算法2.5 单链表的结点插入】 {q=head; while(q->next!=p) q=q->next; s=(slnodetype*)malloc(sizeof(slnodetype)); s->data=x; s->next=p; q->next=s;} P23【算法2.6 单链表的前插入】 int insert(slnodetype *h,int i,Elemtype x) {/*在链表h中，在第i个数据元素前插入一个数据元素x */ slnodetype *p,*q,*s; int j=0; p=h; while(p!=NULL&&j if ((s=(slnodetype*)malloc(sizeof(slnodetype)))==NULL) return FALSE; s->data=x; s->next=p->next; q->next=s; return TRUE;} P23例：下面C程序中的功能是，首先建立一个线性链表head={3，5，7，9}，其元素值依次为从键盘输入正整数（以输入一个非正整数为结束）；在线性表中值为x的元素前插入一个值为y的数据元素。若值为x的结点不存在，则将y插在表尾。 #include \#include \struct slnode {int data; struct slnode *next;} /*定义结点类型*/ main() {int x,y,d; struct slnode *head,*p,*q,*s; head=NULL; /*置链表空*/ q=NULL; scanf(\输入链表数据元素*/ while(d>0) {p=(struct slnode*)malloc(sizeof(struct slnode)); /*申请一个新结点*/ p->data=d; p->next=NULL; if(head==NULL) head=p; /*若链表为空，则将头指针指向当前结点p*/ else q->next=p; /*链表不为空时，则将新结点链接在最后*/ q=p; /*将指针q指向链表的最后一个结点*/ scanf(\ scanf(\ s=(struct slnode*)malloc(sizeof(struct slnode)); s->data=y; q=head;p=q->next; while((p!=NULL)&&(p->data!=x)) {q=p;p=p->next;} /*查找元素为x的指针*/ s->next=p;q->next=s; /*插入元素y*/ } P24【算法2.7 单链表的删除】 int Delet(slnodetype *h,int i) { /*在链表h中删除第i个结点*/ slnodetype *p,*s; int j; p=h;j=0; while(p->next!=NULL&&j { p=p->next;j=j+1; /*寻找第i-1个结点,p指向其前驱*/} if(j!=i-1) {printf(\删除位置错误!*/ return FALSE; } s=p->next; p->next=p->next->next; /*删除第i个结点*/ free(s); /*释放被删除结点空间*/ return TRUE; } P25例：假设已有线性链表La，编制算法将该链表逆置。 void converse(slnodetype *head) {slnodetype *p,*q; p=head->next; head->next=NULL; while(p!=NULL) { q=p->next; p->next=head->next; head->next=p; p=q; } } P27例：将两个循环链表首尾相接。La为第一个循环链表表尾指针，Lb为第二个循环链表表尾指针。合并后Lb为新链表的尾指针。 Void merge(slnodetype *La,slnodetype *Lb) { slnodetype *p; p=La->next; Lb->next= La->next; La->next=p->next; free(p); } P29【算法2.8 双向链表的插入】 int insert_dul(dlnodetype *head,int i,Elemtype x) {/*在带头结点的双向链表中第i个位置之前插入元素x*/ dlnodetype *p,*s; int j; p=head; j=0; while (p!=NULL&&j { printf(\ return FALSE;} if((s=(dlnodetype *)malloc(sizeof(dlnodetype)))==NULL) return FALSE; s->data=x; s->prior=p->prior; /*图中步骤①*/ p->prior->next=s; /*图中步骤②*/ s->next=p; /*图中步骤③*/ p->prior=s; /*图中步骤④*/ return TRUE;} P30【算法2.9 双向链表的删除】 int Delete_dl(dlnodetype *head,int i) { dlnodetype *p,*s; int j; p=head; j=0; while (p!=NULL&&j { printf(\