清華嚴(yán)蔚敏《大數(shù)據(jù)結(jié)構(gòu)》地全部代碼實(shí)現(xiàn)C語(yǔ)言
《清華嚴(yán)蔚敏《大數(shù)據(jù)結(jié)構(gòu)》地全部代碼實(shí)現(xiàn)C語(yǔ)言》由會(huì)員分享，可在線閱讀，更多相關(guān)《清華嚴(yán)蔚敏《大數(shù)據(jù)結(jié)構(gòu)》地全部代碼實(shí)現(xiàn)C語(yǔ)言（51頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。
1、/* cl.h （程序名）*/
#in elude
2、() */
#in clude
3、n 是布爾類型，其值是 TRUE或 FALSE */ /* algo2-1.c 實(shí)現(xiàn)算法2.1的程序*/ #include "cl.h" typedef int ElemType; #include "c2-1.h" /*c2-1.h 線性表的動(dòng)態(tài)分配順序存儲(chǔ)結(jié)構(gòu) */ #define LIST_INIT_SIZE 10 /*線性表存儲(chǔ)空間的初始分配量 */ #define LISTINCREMENT 2/* 線性表存儲(chǔ)空間的分配增量 */ typedef struct { ElemType *elem; /* 存儲(chǔ)空間基址 */ int length ; /* 當(dāng)前長(zhǎng)度
4、 */ int listsize ; /* 當(dāng)前分配的存儲(chǔ)容量 (以sizeof( ElemType)為單位)*/ } SqList ; #include "bo2-1.c" /* bo2-1.c 順序表示的線性表(存儲(chǔ)結(jié)構(gòu)由c2-1.h定義)的基本操作(12個(gè))*/ Status InitList (SqList *L) /* 算法 2.3 */ { /*操作結(jié)果：構(gòu)造一個(gè)空的順序線性表 */ (*L). elem=( ElemType*) malloc (LIST_INIT_SIZE *sizeof ( ElemType)); if (!( *L). elem) exit
5、(OVERFLOW);/* 存儲(chǔ)分配失敗 */ (*L). length =0; /* 空表長(zhǎng)度為 0 */ (*L). listsize =LIST_INIT_SIZE ; /* 初始存儲(chǔ)容量 */ return OK; } Status DestroyList (SqList *L) { /*初始條件：順序線性表 L已存在。操作結(jié)果：銷毀順序線性表 L */ free(( *L). elem); (*L). elem=NULL; (*L). length =0; (*L). listsize =0; return OK; } Stat
6、us ClearList (SqList *L) { /*初始條件：順序線性表 L已存在。操作結(jié)果：將 L重置為空表*/ (*L). length =0; return OK; } Status ListEmpty (SqList L) { /*初始條件：順序線性表 L已存在。操作結(jié)果：若 L為空表，則返回 TRUE否則返回 FALSE */ if (L. length ==0) return TRUE; else return FALSE; } int List Length (SqList L) { /*初始條件：順序線性表 L已存在。操作結(jié)果：返回 L中
7、數(shù)據(jù)元素個(gè)數(shù)*/ return L. length ; } Status Get Elem( SqList L, int i, ElemType *e) { /*初始條件：順序線性表 L已存在，1 < i w ListLength(L) */ /*操作結(jié)果：用e返回L中第i個(gè)數(shù)據(jù)元素的值*/ if (i<1||i>L. length ) exit (ERROR); *e=*(L. elem+i-1); return OK; } int Locate Elem( SqList L, ElemType e, Status (*compare)( ElemType, ElemT
8、ype)) { /*初始條件：順序線性表 L已存在，compare()是數(shù)據(jù)元素判定函數(shù)(滿足為1,否則為 0) */ /*操作結(jié)果：返回L中第1個(gè)與e滿足關(guān)系compare()的數(shù)據(jù)元素的位序。 */ /* 若這樣的數(shù)據(jù)元素不存在，則返回值為 0。算法2.6 */ ElemType *p; int i=1; /* i的初值為第1個(gè)元素的位序*/ p=L. elem; /* p的初值為第1個(gè)元素的存儲(chǔ)位置*/ while (i<=L. length &&!compare(*p++,e)) ++i; if (i<=L. length ) return i; else r
9、eturn 0; } Status Prior Elem( SqList L, ElemType cur_e, ElemType *pre_e) { /*初始條件：順序線性表 L已存在*/ /*操作結(jié)果：若cur_e是L的數(shù)據(jù)元素，且不是第一個(gè)，則用pre_e返回它的前驅(qū)，*/ /* 否則操作失敗，pre_e無(wú)定義*/ int i=2; ElemType *p=L. elem+1; while (i<=L. length &&*p!=cur_e) { p++； i++； } if (i>L. length ) return INFEASIBLE; else {
10、*pre_e=*--p;
return OK;
}
}
Status Next Elem(SqList L, ElemType cur_e, ElemType *next_e)
{ /*初始條件：順序線性表 L已存在*/
/*操作結(jié)果：若cur_e是L的數(shù)據(jù)元素，且不是最后一個(gè)，則用next_e返回它的后繼, */
/* 否則操作失敗，next_e無(wú)定義*/
int i=1;
ElemType *p=L. elem;
while (i 11、NFEASIBLE;
else
{
*n ext_e=*++p;
return OK;
}
}
Status List In sert( SqList *L, i nt i, ElemType e) /* 算法 2.4 */
{ /*初始條件：順序線性表 L已存在，1 < i < ListLength(L)+1 */
/*操作結(jié)果：在L中第i個(gè)位置之前插入新的數(shù)據(jù)元素 e, L的長(zhǎng)度加1 */
ElemType *n ewbase,*q,*p;
if (i<1||i>( *L). length +1) /* i 值不合法 */
return ERROR;
if (( 12、*L). length >=(*L). listsize ) /*當(dāng)前存儲(chǔ)空間已滿，增加分配*/
{
n ewbase=( ElemType
*)realloc(( *L). elem,(( *L). listsize +LISTINCREMENT)Sizeof (ElemType));
if (!newbase)
exit (OVERFLOW); /* 存儲(chǔ)分配失敗 */
( *L). elem =newbase; /* 新基址 */
(*L). listsize +=LISTINCREMENT;/* 增加存儲(chǔ)容量 */
}
q=( *L). elem+i-1; /* q 13、為插入位置 */
for (p=( *L). elem+(*L). length -1;p>=q;--p) /* 插入位置及之后的元素右移 */
*(p+1)=*p;
*q=e; /* 插入 e */
++( *L). length ; /* 表長(zhǎng)增 1 */
return OK;
}
Status ListDelete( SqList *L, int i, ElemType *e) /* 算法 2.5 */
{ /*初始條件：順序線性表 L已存在，1 < i < ListLength(L) */
/*操作結(jié)果：刪除L的第i個(gè)數(shù)據(jù)元素，并用 e返回其值，L的長(zhǎng)度減1 */
14、ElemType *p,*q;
if (i<1||i>( *L). length ) /* i 值不合法 */
return ERROR;
p=( *L). elem+i-1; /* p為被刪除元素的位置 */
*e=*p; /*被刪除元素的值賦給 e */
q=( *L). elem+(*L). length -1; /* 表尾元素的位置 */
for什+p;p<=q;++p) /*被刪除元素之后的元素左移 */
*(p-1)=*p;
(*L). length --; /* 表長(zhǎng)減 1 */
return OK;
}
Status ListTraverse( SqLis 15、t L,void(*vi)( ElemType*))
{ /*初始條件：順序線性表 L已存在*/
/*操作結(jié)果：依次對(duì)L的每個(gè)數(shù)據(jù)元素調(diào)用函數(shù) vi()。一旦vi()失敗，則操作失敗*/
/* vi() 的形參加& ,表明可通過(guò)調(diào)用 vi()改變?cè)氐闹?/
ElemType *p;
int i;
p=L. elem;
for (i=1;i<=L. length ;i++)
vi(p++);
pr int f("\n");
return OK;
}
Status equal( ElemType c1, ElemType c2)
{ /*判斷是否相等的函數(shù)， Union 16、()用到*/
if (c1==c2)
return TRUE;
else
return FALSE;
}
void Union( SqList *La, SqList Lb) /* 算法 2.1 */
{ /*將所有在線性表Lb中但不在La中的數(shù)據(jù)元素插入到 La中*/
ElemType e;
int La_len,Lb_len;
int i;
La_len=List Length (*L a); /* 求線性表的長(zhǎng)度 */
Lb_len=List Length (Lb);
for (i=1;i<=Lb_len;i++)
{
Get Elem(Lb,i,&e); 17、/*取Lb中第i個(gè)數(shù)據(jù)元素賦給 e */
if (!Locate Elem( *La,e,equal)) /* La 中不存在和e相同的元素，則插入之*/ ListI nsert(La,++La_le n, e);
}
}
void pr int (ElemType *c)
{
pr int f("%d ",*c);
}
void mai n()
{
SqList La,Lb;
Status i;
int j;
i= In itList (&La);
if (i==1) /* 創(chuàng)建空表 La成功*/
for (j=1;j<=5;j++) /*在表La中插入5個(gè)元素 18、*/
i=List In sert(&La,j,j);
pr int f("La= "); /* 輸出表 La 的內(nèi)容 */
ListTraverse(La,pr int );
InitList (&Lb); /*也可不判斷是否創(chuàng)建成功 */
for (j=1;j<=5;j++) /* 在表Lb中插入5個(gè)元素*/
i=ListI nsert(&Lb,j,2*j);
pr int f("Lb= "); /* 輸出表 Lb 的內(nèi)容 */
ListTraverse(Lb,pr int );
Un io n(&La,Lb);
pr int f("new La= "); /* 輸出新 19、表 La 的內(nèi)容 */
ListTraverse(La,pr
int );}
/* algo2-2.c 實(shí)現(xiàn)算法 22的程序*/
#include "cl.h"
typedef int ElemType;
#include "c2-1.h"
#include "bo2-1.c" void MergeList( SqList La, SqList Lb, SqList *Lc) /* 算法 2.2 */
{ /*已知線性表La和Lb中的數(shù)據(jù)元素按值非遞減排列。 */
/*歸并La和Lb得到新的線性表 Lc,Lc的數(shù)據(jù)元素也按值非遞減排列 */
int i= 20、1,j=1,k=O;
int La_len,Lb_len;
ElemType ai,bj;
InitList (Lc); /* 創(chuàng)建空表 Lc */
La_len=List Length (La);
Lb_len=List Length (Lb);
while (i<=La_len&&j<=Lb_len) /* 表 La 和表 Lb 均非空 */
{
Get Elem(La,i, &ai);
Get Elem(Lb,j, &bj);
if (ai<=bj)
{
List In sert(Lc,++k,ai);
++i;
}
else
{
ListI nsert 21、(Lc,++k,bj);
++j;
}
}
while (i<=La_len) /* 表 La 非空且表 Lb 空 */
{
Get Elem(La,i++, &ai);
List In sert(Lc,++k,ai);
}
while (j<=Lb_len) /* 表 Lb 非空且表 La 空 */
{
Get Elem(Lb,j++, &bj);
ListI nsert(Lc,++k,bj);
}
}
void pr int (ElemType *c)
{
pr int f("%d ",*c);
}
void mai n()
{
SqList La 22、,Lb,Lc;
int j,a[4]={3,5,8,11},b[7]={2,6,8,9,11,15,20};
In itList (&La);
/*
創(chuàng)建空表
La */
for (j=1;j<=4;j++)
/*在表La中插入
4個(gè)兀素*/
ListI nsert(&La,j,a[j-1]);
pr int f("La=");
/*
輸出表
La的內(nèi)容
*/
ListTraverse(La,pr
int );
In itList (&Lb);
/*
創(chuàng)建空表
Lb */
for (j=1;j<=7;j++) / 23、* 在表Lb中插入7個(gè)元素*/
ListI nsert(&Lb,j,b[j-1]);
pr int f("Lb= "); /* 輸出表 Lb 的內(nèi)容 */
ListTraverse(Lb,pr int );
MergeList(La,Lb,&Lc);
pr int f("Lc= "); /* 輸出表 Lc 的內(nèi)容 */
ListTraverse(Lc,pr int );
}
/* algo2-3.c 實(shí)現(xiàn)算法2.7的程序*/
#include "cl.h"
typedef int ElemType;
#include "c2-1.h"
#include "bo2-1.c 24、"
void MergeList( SqList La, SqList Lb, SqList *Lc) /* 算法 2.7 */
{ /*已知順序線性表 La和Lb的元素按值非遞減排列。 */
/*歸并La和Lb得到新的順序線性表 Lc,Lc的元素也按值非遞減排列 */
ElemType *pa,*pa_last,*pb,*pb_last,*pc;
pa=La. elem;
pb=Lb. elem;
Lc
(*Lc). listsize =(*Lc). length =La. length +Lb. length ; /* 不用 InitList() 創(chuàng)建空表
*/
pc= 25、( *Lc). elem =( ElemType *) malloc (( *Lc). listsize * sizeof (ElemType));
if (!( *Lc). elem) /* 存儲(chǔ)分配失敗 */
exit (OVERFLOW);
pa_last=La. elem+La. length -1;
pb_last=Lb. elem+Lb. length -1;
while (pa<=pa_last&&pb<=pb_last) /* 表 La 和表 Lb 均非空 */
{ /*歸并*/
if (*pa<=*pb)
*pc++=*pa++;
else
*pc++=* 26、pb++;
while (pa<=pa_last)
*pc++=*pa++; /*
while (pb<=pb_last)
*pc++=*pb++; /*
/*表La非空且表Lb空*/ 插入La的剩余元素*/
/* 表Lb非空且表 La空*/
插入Lb的剩余元素*/
void pr int (ElemType *c)
{
pr int f("%d ",*c);
}
void mai n()
{
SqList La,Lb,Lc;
int j;
InitList (&La); /* 創(chuàng)建空表 La */
for (j=1;j<=5;j++) /* 在表La中插 27、入5個(gè)元素*/
ListI nsert (&La,j,j);
pr int f("La= "); /* 輸出表 La 的內(nèi)容 */
ListTraverse(La,pr int );
InitList (&Lb); /* 創(chuàng)建空表 Lb */
for (j=1;j<=5;j++) /* 在表Lb中插入5個(gè)元素*/
ListI nsert(&Lb,j,2*j);
pr int f("Lb= "); /* 輸出表 Lb 的內(nèi)容 */
ListTraverse(Lb,pr int );
MergeList(La,Lb,&Lc);
pr int f("Lc= "); /* 輸出表 28、Lc 的內(nèi)容 */
ListTraverse(Lc,pr int );
}
/* algo2-4.c 修改算法2.7的第一個(gè)循環(huán)語(yǔ)句中的條件語(yǔ)句為開(kāi)關(guān)語(yǔ)句，且當(dāng) */ /* *pa=*pb 時(shí)，只將兩者中之一插入 Lc。此操作的結(jié)果和算法 2.1相同*/
#include "c1.h" typedef int ElemType;
#include "c2-1.h"
#include "bo2-1.c"
int comp( ElemType c1, ElemType c2) {
int i;
if (c1 29、lse
i=-1;
return i;
}
void MergeList( SqList La, SqList Lb, SqList *Lc)
{ /*另一種合并線性表的方法(根據(jù)算法 2.7下的要求修改算法 2.7 ) */
ElemType *pa,*pa_last,*pb,*pb_last,*pc;
pa=La. elem;
pb=Lb. elem;
(*Lc). listsize =La. length +Lb. length ; /* 此句與算法 2.7 不同 */
pc=( *Lc). elem =( ElemType *) malloc (( *Lc). li 30、stsize * sizeof (ElemType)); if (!( *Lc). elem)
exit (OVERFLOW);
pa_last=La. elem+La. length -1;
pb_last=Lb. elem+Lb. length -1;
while (pa<=pa_last&&pb<=pb_last) /* 表 La 和表 Lb 均非空 */
switch(comp(*pa,*pb)) /* 此句與算法 2.7 不同 */
{
case 0: pb++;
case 1:*pc++=*pa++;
break;
case -1:*pc++=*pb++;
} 31、
while (pa<=pa_last) /* 表 La 非空且表 Lb 空 */
*pc++=*pa++;
while (pb<=pb_last) /* 表 Lb 非空且表 La 空 */
*pc++=*pb++;
(*Lc). length =pc-( *Lc). elem; /* 加此句 */
}
void pr int (ElemType *c) {
pr int f("%d ",*c);
}
void mai n()
{
SqList La,Lb,Lc;
int j;
InitList (&La); /* 創(chuàng)建空表 La */
for (j=1；j<=5 32、;j++) /* 在表La中插入5個(gè)元素*/
ListI nsert (&La,j,j);
pr int f("La= "); /* 輸出表 La 的內(nèi)容 */
ListTraverse(La,pr int );
InitList (&Lb); /* 創(chuàng)建空表 Lb */
for (j=1;j<=5;j++) /* 在表Lb中插入5個(gè)元素*/
ListI nsert(&Lb,j,2*j);
pr int f("Lb= "); /* 輸出表 Lb 的內(nèi)容 */
ListTraverse(Lb,pr int );
MergeList(La,Lb,&Lc);
pr int f(" 33、Lc= "); /* 輸出表 Lc 的內(nèi)容 */
ListTraverse(Lc,pr int );
}
/* algo2-5.c 實(shí)現(xiàn)算法 2.11、2.12 的程序 */
#include "cl.h"
typedef int ElemType;
#include "c2-2.h"
/* c2-2.h 線性表的單鏈表存儲(chǔ)結(jié)構(gòu) */
struct LNode
{
ElemType data;
struct LNode *n ext;
}；
typedef struct LNode *L inkList; /* 另一種定義 LinkList 的方法 */ #inclu 34、de "bo2-2.c"
/* bo2-2.c 單鏈表線性表(存儲(chǔ)結(jié)構(gòu)由c2-2.h定義)的基本操作(12個(gè))*/
Status In itList (Lin kList *L)
{ /*操作結(jié)果：構(gòu)造一個(gè)空的線性表 L */
*L=(LinkList) malloc ( sizeof ( struct LNode)); /* 產(chǎn)生頭結(jié)點(diǎn)，并使 L 指向此頭結(jié)點(diǎn) */
if (! *L) /*存儲(chǔ)分配失敗*/
exit (OVERFLOW);
(*L)->next=NULL; /* 指針域?yàn)榭?*/
return OK;
}
Status DestroyList (Li n 35、kList *L)
{ /*初始條件：線性表 L已存在。操作結(jié)果：銷毀線性表 L */
Lin kList q;
while (*L)
{
q=( *L)-> next;
free( *L);
*L=q;
}
return OK;
}
Status ClearList (LinkList L) /* 不改變 L */
{ /*初始條件：線性表 L已存在。操作結(jié)果：將 L重置為空表*/
Lin kList p,q;
p=L-> next; /* p指向第一個(gè)結(jié)點(diǎn) */
while (p) /* 沒(méi)到表尾*/
{
q=p->n ext;
free(p);
p= 36、q;
}
L-> next=NULL; /*頭結(jié)點(diǎn)指針域?yàn)榭?*/
return OK;
}
Status ListEmpty (LinkList L)
{ /*初始條件：線性表 L已存在。操作結(jié)果：若 L為空表，則返回TRUE否則返回FALSE
*/
if (L->next) /* 非空 */
return FALSE;
else
return TRUE;
}
int List Length (LinkList L)
{ /*初始條件：線性表 L已存在。操作結(jié)果：返回 L中數(shù)據(jù)元素個(gè)數(shù)*/
int i=0;
Lin kList p=L-> next; /* p 37、 指向第一個(gè)結(jié)點(diǎn) */
while (p) /* 沒(méi)到表尾*/
{
i++;
p=p->n ext;
}
return i;
}
Status Get Elem(LinkList L, int i, ElemType *e) /* 算法 2.8 */
{ /* L為帶頭結(jié)點(diǎn)的單鏈表的頭指針。當(dāng)?shù)?i個(gè)元素存在時(shí)，其值賦給e并返回OK,否則
返回 ERROR */
int j=1; /* j 為計(jì)數(shù)器*/
Lin kList p=L-> next; /* p 指向第一個(gè)結(jié)點(diǎn) */
while (p&&j 38、
p=p->n ext;
j++;
}
if (!p||j>i) /*第i個(gè)元素不存在*/
return ERROR;
*e=p->data; /* 取第 i 個(gè)元素 */
return OK;
}
int Locate Elem(LinkList L, ElemType e, Status (*compare)( ElemType, ElemType))
{ /*初始條件：線性表L已存在,compare()是數(shù)據(jù)元素判定函數(shù)(滿足為1,否則為0) */ /*操作結(jié)果：返回L中第1個(gè)與e滿足關(guān)系compare。的數(shù)據(jù)元素的位序。 */
/* 若這樣的數(shù)據(jù)元素不存在,則返回值 39、為0 */
int i=0;
Lin kList p=L->n ext;
while (p)
{
i++；
if (compare(p->data,e)) /*找到這樣的數(shù)據(jù)元素 */
return i;
p=p->n ext;
}
return 0;
}
Status Prior Elem(LinkList L, ElemType cur_e, ElemType *pre_e)
{ /*初始條件：線性表L已存在*/
/*操作結(jié)果：若cur_e是L的數(shù)據(jù)元素，且不是第一個(gè)，則用pre_e返回它的前驅(qū)，*/
/* 返回OK;否則操作失敗,pre_e無(wú)定義，返回INF 40、EASIBLE */
Lin kList q,p=L-> next; /* p 指向第一個(gè)結(jié)點(diǎn) */
while (p->next) /* p所指結(jié)點(diǎn)有后繼 */
{
q=p->next; /* q 為 p 的后繼 */
if (q->data==cur_e)
{
*pre_e=p->data;
return OK;
}
p=q; /* p 向后移*/
}
return INFEASIBLE;
}
Status Next Elem(LinkList L, ElemType cur_e, ElemType *next_e)
{ /*初始條件：線性表 L已存在*/
41、/*操作結(jié)果：若cur_e是L的數(shù)據(jù)元素，且不是最后一個(gè)，則用next_e返回它的后繼,
*/
/* 返回OK;否則操作失敗，next_e無(wú)定義，返回INFEASIBLE */
Lin kList p=L-> next; /* p 指向第一個(gè)結(jié)點(diǎn) */
while (p->next) /* p所指結(jié)點(diǎn)有后繼 */
{
if (p->data==cur_e)
{
*n ext_e=p->n ext->data;
return OK;
}
p=p->n ext;
}
return INFEASIBLE;
}
Status List In sert(Li nkList 42、L, int i, ElemType e) /* 算法 2.9。不改變 L */
{ /*在帶頭結(jié)點(diǎn)的單鏈線性表 L中第i個(gè)位置之前插入元素 e */
int j=0;
Lin kList p=L,s;
while (p&&j 43、>n ext=p->n ext;
p_>n ext=s;
return OK;
}
Status ListDelete(LinkList L, int i, ElemType *e) /* 算法 2.10。不改變 L */
{ /*在帶頭結(jié)點(diǎn)的單鏈線性表 L中，刪除第i個(gè)元素，并由e返回其值*/
int j=0;
Lin kList p=L,q;
while (p->next&&j 44、R;
q=p->next; /*刪除并釋放結(jié)點(diǎn)*/
p_>n ext=q _>n ext;
*e=q_>data;
free(q);
return OK;
}
Status ListTraverse(LinkList L,void(*vi)( ElemType))
/* vi 的形參類型為 ElemType，與bo2-1.c中相應(yīng)函數(shù)的形參類型 ElemType&不同*/
{ /*初始條件：線性表 L已存在*/
/*操作結(jié)果：依次對(duì)L的每個(gè)數(shù)據(jù)元素調(diào)用函數(shù) vi()。一旦vi()失敗，則操作失敗*/
Lin kList p=L->n ext;
while (p)
{
45、
vi(p->data);
p=p->n ext;
}
pr int f("\n");
return OK;
}
void CreateList(LinkList *L, int n) /* 算法 2.11 */
{ /*逆位序(插在表頭)輸入n個(gè)元素的值，建立帶表頭結(jié)構(gòu)的單鏈線性表 L */
int i;
Lin kList p;
*L=(LinkList) malloc (sizeof (struct LNode));
(*L)-> next=NULL; /* 先建立一個(gè)帶頭結(jié)點(diǎn)的單鏈表 */
pr int f("請(qǐng)輸入％d個(gè)數(shù)據(jù)\n",n);
for (i=n; 46、i>0;__i)
{
p=(LinkList) malloc (sizeof (struct LNode)); /* 生成新結(jié)點(diǎn) */
scanf("%d",&p->data); /* 輸入元素值 */
p->next=( *L )->next; /* 插入到表頭 */
( *L)->n ext=p;
}
}
void CreateList2(LinkList *L, int n)
{ /*正位序(插在表尾)輸入n個(gè)元素的值，建立帶表頭結(jié)構(gòu)的單鏈線性表 */
int i;
Lin kList p,q;
*L=(LinkList) malloc (sizeof (stru 47、ct LNode)); /* 生成頭結(jié)點(diǎn) */
(*L)-> next=NULL;
q= *L;
pr int f("請(qǐng)輸入％d個(gè)數(shù)據(jù)\n",n);
for (i=1;i<=n;i++)
{
p=(LinkList) malloc (sizeof (struct LNode));
scan f("%d",&p->data);
q_>n ext=p;
q=q_>n ext;
}
p-> next=NULL;
}
void MergeList(LinkList La,LinkList *Lb,LinkList *Lc)/* 算法 2.12 */
{ /*已知單鏈線性表 48、La和Lb的元素按值非遞減排列。 */
/*歸并La和Lb得到新的單鏈線性表 Lc，Lc的元素也按值非遞減排列 */
LinkList pa=La->next,pb=( *L b)->next,pc;
*Lc=pc=La; /*用La的頭結(jié)點(diǎn)作為 Lc的頭結(jié)點(diǎn)*/
while (pa&&pb)
if (pa->data<=pb->data)
{
pc- >n ext=pa;
pc=pa;
pa=pa->n ext;
}
else
{
pc- >n ext=pb;
pc=pb;
pb=pb->n ext;
}
pc->next=pa?pa:pb; /* 插入剩余 49、段 */
free( *Lb); /*釋放Lb的頭結(jié)點(diǎn)*/
Lb=NULL;
}
void visit( ElemType c) /* ListTraverse() 調(diào)用的函數(shù)(類型要一致)*/
{
pr int f("%d ”,c);
}
void mai n()
{
int n=5;
Lin kList La,Lb,Lc;
pr int f("按非遞減順序，");
CreateList2(&La,n); /*正位序輸入 n個(gè)元素的值*/
pr int f("La="); /*輸出鏈表La的內(nèi)容*/
ListTraverse(La,visit);
pr int 50、 f("按非遞增順序，");
CreateList(&Lb,n); /* 逆位序輸入 n個(gè)元素的值*/
pr int f("Lb="); /*輸出鏈表Lb的內(nèi)容*/
ListTraverse(Lb,visit);
MergeList(La,&Lb,&Lc); /* 按非遞減順序歸并 La和Lb,得到新表Lc */
pr int f("Lc="); /*輸出鏈表Lc的內(nèi)容*/
ListTraverse(Lc,visit);
}
/* algo2-6.c 利用單鏈表結(jié)構(gòu)處理教科書(shū)圖 2.1(學(xué)生健康登記表)*/
#include "c1.h"
#defi ne NAMELEN 51、8 /* 姓名最大長(zhǎng)度 */
#defi ne CLASSLEN 4 /* 班級(jí)名最大長(zhǎng)度 */
struct stud /* 記錄的結(jié)構(gòu)*/
{
char name[NAMELEN+1];
long num;
char sex;
int age;
char Class[CLASSLEN+1];
int health;
};
typedef struct stud ElemType; /*鏈表結(jié)點(diǎn)元素類型為結(jié)構(gòu)體 */
#include "c2-2.h"
char sta[3][9]={" 健康"，” 一般"，”神經(jīng)衰弱"}; /*健康狀況(3類)*/
FILE * 52、fp;
Status InitList (LinkList *L) /* 拷自 bo2-2.c */
{ /*操作結(jié)果：構(gòu)造一個(gè)空的線性表 L */
*L=(LinkList) malloc (sizeof (struct LNode)); /* 產(chǎn)生頭結(jié)點(diǎn)，并使 L 指向此頭結(jié)點(diǎn)
*/
if (! *L) /*存儲(chǔ)分配失敗*/
exit (OVERFLOW);
(*L)->next=NULL; /* 指針域?yàn)榭?*/
return OK;
}
Status ListTraverse(LinkList L,void(*vi)( ElemType)) /* 拷自 bo2-2. 53、c */
{ /*初始條件：線性表 L已存在*/
/*操作結(jié)果：依次對(duì)L的每個(gè)數(shù)據(jù)元素調(diào)用函數(shù) vi()。一旦vi()失敗，則操作失敗*/
Lin kList p=L->n ext;
while (p)
{
vi(p->data);
p=p->n ext;
}
pr int f("\n");
return OK;
}
void In sertAsce nd(Li nkList L, ElemType e) /* 此函數(shù)是由 bo2-9.c 中的同名函數(shù)改寫(xiě)
*/
{ /*按學(xué)號(hào)非降序插入*/
Lin kList q=L,p=L->n ext;
while (p& 54、&e.num>p->data.num)
{
q=p；
p=p->n ext;
}
q->next=(LinkList) malloc (sizeof (struct LNode)); /* 插在 q 后 */
q->n ext->data=e;
q_>n ext- >n ext=p;
} void Print (struct stud e)
{ /*顯示記錄e的內(nèi)容*/
pr int f("%-8s %6ld",e.name,e.num);
if (e.sex=='m')
pr int f("男");
else
pr int f("女");
pr int f("% 55、5d %-4s",e.age,e.Class);
pr int f("%9s\n",sta[e.health]);
}
void Readln( struct stud *e)
{ /*由鍵盤(pán)輸入結(jié)點(diǎn)信息 */
pr int f("請(qǐng)輸入姓名(<=%d個(gè)字符):",NAMELEN);
sca nf("%s",e->n ame);
pr int f("請(qǐng)輸入學(xué)號(hào):");
sca nf("%ld", &e-> nu m);
pr int f("請(qǐng)輸入性別(m:男f:女):");
sca nf("%*c%c", &e->sex);
pr int f("請(qǐng)輸入年齡:");
sc 56、a nf("%d", &e->age);
pr int f("請(qǐng)輸入班級(jí)(<=%d個(gè)字符):",CLASSLEN);
sca nf("%s",e->Class);
pr int f("請(qǐng)輸入健康狀況(0:%s 1:%s 2:%s):",sta[0],sta[1],sta[2]); sca nf("%d", &e->health);
}
void WriteToFile( struct stud e)
{ /*將結(jié)點(diǎn)信息寫(xiě)入fp指定的文件*/
fwrite(&e, sizeof (struct stud),1,fp);
}
Status ReadFromFile( struct 57、 stud *e)
{ /*由fp指定的文件讀取結(jié)點(diǎn)信息到 e */
int i;
i=fread(e, sizeof (struct stud),1,fp);
if (i==1) /* 讀取文件成功*/
return OK;
else
return ERROR;
}
Status FindFromNum(LinkList L,long num,LinkList *p,LinkList *q)
{ /*查找表中學(xué)號(hào)為num的結(jié)點(diǎn)，如找到,q指向此結(jié)點(diǎn),p指向q的前驅(qū),*/
/*并返回TRUE如無(wú)此元素，則返回FALSE */
*p=L;
while (*p)
{
58、*q=(*p)-> next;
if (*q&&(*q)->data.num>num) /*因?yàn)槭前磳W(xué)號(hào)非降序排列 */
break;
if (*q&&(*q)->data.num==num) /* 找到該學(xué)號(hào) */
return TRUE;
*p=*q;
}
return FALSE;
}
Status FindFromName(LinkList L,char name[],LinkList *p,LinkList *q)
{ /*查找表中姓名為name的結(jié)點(diǎn)，如找到,q指向此結(jié)點(diǎn),p指向q的前驅(qū)，*/
/*并返回TRUE如無(wú)此元素，則返回FALSE */
*p=L; 59、
while (*p)
{
*q=(*p)-> next;
if (*q&&!strcmp((*q)->data.name,name)) /* 找到該姓名 */
return TRUE;
*p=*q;
FALSE;
} return
Status Delete ElemNum(LinkList L,long num)
{ /*刪除表中學(xué)號(hào)為num的元素，并返回TRUE如無(wú)此元素，則返回 FALSE */
Lin kList p,q;
if (FindFromNum(L,num,&p,&q)) /*找到此結(jié)點(diǎn)，且q指向其,p指向其前驅(qū)*/
{
p_>n ext=q _ 60、>n ext;
free(q);
return TRUE;
}
return FALSE;
}
Status Delete ElemName(LinkList L,char name[])
{ /*刪除表中姓名為name的元素，并返回 TRUE如無(wú)此元素，則返回 FALSE */
Lin kList p,q;
if (FindFromName(L,name,&p,&q)) /* 找到此結(jié)點(diǎn)，且q指向其,p指向其前驅(qū)*/
{
p_>n ext=q _>n ext;
free(q);
return TRUE;
}
return FALSE;
}
void Modf 61、 y( ElemType *e)
{ /*修改結(jié)點(diǎn)內(nèi)容*/
char s[80];
Pr int (*e); /* 顯示原內(nèi)容 */
pr int f("請(qǐng)輸入待修改項(xiàng)的內(nèi)容，不修改的項(xiàng)按回車鍵保持原值 :\n");
pr int f("請(qǐng)輸入姓名(<=%d個(gè)字符):",NAMELEN);
gets(s);
if (strlen(s))
strcpy(e->n ame,s);
pr int f("請(qǐng)輸入學(xué)號(hào):");
gets(s);
if (strlen(s))
e->num=atol(s);
pr int f("請(qǐng)輸入性別(m:男f:女):");
gets(s); 62、
if (strlen(s))
e_>sex=s[0];
pr int f("請(qǐng)輸入年齡:");
gets(s);
if (strlen(s))
e_>age=atoi(s);
pr int f("請(qǐng)輸入班級(jí)(<=%d個(gè)字符):",CLASSLEN); gets(s);
if (strlen(s))
strcpy(e->Class,s);
pr int f("請(qǐng)輸入健康狀況(0:%s 1:%s 2:%s):",sta[0],sta[1],sta[2]); gets(s);
if (strlen(s))
e->health=atoi(s); /* 修改完畢 */
}
63、#define N 4 /* student 記錄的個(gè)數(shù) */
void mai n()
{
struct stud stude nt[N]={{"
王小林",790631,'m',18,"
計(jì) 91",0},
{"
陳紅",790632,'f,20,"
計(jì) 91",1},
{"
劉建平",790633,'m',21,"
計(jì) 91",0},
{"
*/
張立立",790634,'m',17,"
計(jì)91",2}}; /*表的初始記錄
int i,j,flag=1;
long num;
char file name[13], name[NAMELEN+1]; 64、
ElemType e;
Lin kList T,p,q;
InitList （&T）; /* 初始化鏈表 */
while （flag）
{
pr int f（"1:將結(jié)構(gòu)體數(shù)組student中的記錄按學(xué)號(hào)非降序插入鏈表 \n"）;
pr int f（"2:將文件中的記錄按學(xué)號(hào)非降序插入鏈表 \n"）;
pr int f（"3:鍵盤(pán)輸入新記錄，并將其按學(xué)號(hào)非降序插入鏈表 \n"）;
pr int f（"4:刪除鏈表中第一個(gè)有給定學(xué)號(hào)的記錄 \n"）;
pr int f（"5:刪除鏈表中第一個(gè)有給定姓名的記錄 \n”）；
pr int f（"6:修改鏈表中第一個(gè)有給定學(xué)號(hào) 65、的記錄 \n”）；
pr int f（"7:修改鏈表中第一個(gè)有給定姓名的記錄 \n"）;
pr int f（"8:查找鏈表中第一個(gè)有給定學(xué)號(hào)的記錄 \n"）;
pr int f（"9:查找鏈表中第一個(gè)有給定姓名的記錄 \n”）；
pr int f（"10:顯示所有記錄11:將鏈表中的所有記錄存入文件 12:結(jié)束\n"）;
pr int f（"請(qǐng)選擇操作命令:"）;
scan f（"%d",&i）;
switch（i）
{
case 1: for （j=0;j 66、int f("請(qǐng)輸入文件名：”)；
sea nf("%s",file name);
if ((fp=fopen(filename,"rb"))==NULL)
pr int f("打開(kāi)文件失敗!\n");
else
{
while (ReadFromFile(&e))
In sertAsce nd(T,e);
fclose(fp);
}
break;
case 3: ReadI n(& e);
In sertAsce nd(T,e);
break;
case 4: pr int f("請(qǐng)輸入待刪除記錄的學(xué)號(hào) :");
scan f("%ld", &nu m);
if (!Delete ElemNum(T,num))
pr int f("沒(méi)有學(xué)號(hào)為 %ld的記錄\n",num);
break;
case 5: pr int f("請(qǐng)輸入待刪除記錄的姓名 :");
sca nf("%s", name);
if (!Delete ElemName(T,name))
pr int f("沒(méi)有姓名為 %s的記錄\n”,name);
break;
ca
- 溫馨提示:
1: 本站所有資源如無(wú)特殊說(shuō)明，都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
2: 本站的文檔不包含任何第三方提供的附件圖紙等，如果需要附件，請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
3.本站RAR壓縮包中若帶圖紙，網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽，若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
5. 裝配圖網(wǎng)僅提供信息存儲(chǔ)空間，僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理，對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯，并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容，請(qǐng)與我們聯(lián)系，我們立即糾正。
7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 6.煤礦安全生產(chǎn)科普知識(shí)競(jìng)賽題含答案
- 2.煤礦爆破工技能鑒定試題含答案
- 3.爆破工培訓(xùn)考試試題含答案
- 2.煤礦安全監(jiān)察人員模擬考試題庫(kù)試卷含答案
- 3.金屬非金屬礦山安全管理人員（地下礦山）安全生產(chǎn)模擬考試題庫(kù)試卷含答案
- 4.煤礦特種作業(yè)人員井下電鉗工模擬考試題庫(kù)試卷含答案
- 1 煤礦安全生產(chǎn)及管理知識(shí)測(cè)試題庫(kù)及答案
- 2 各種煤礦安全考試試題含答案
- 1 煤礦安全檢查考試題
- 1 井下放炮員練習(xí)題含答案
- 2煤礦安全監(jiān)測(cè)工種技術(shù)比武題庫(kù)含解析
- 1 礦山應(yīng)急救援安全知識(shí)競(jìng)賽試題
- 1 礦井泵工考試練習(xí)題含答案
- 2煤礦爆破工考試復(fù)習(xí)題含答案
- 1 各種煤礦安全考試試題含答案
相關(guān)資源
更多