数据结构绪论第一章算法汇总

1. AUB 将所有在Lb中但不在La中的数据元素插入到La中 Void Union（ List &La， List Lb） ｛ La_len=ListLength（La）； Lb_len=ListLength（Lb）； For（i=1；i<=Lb_len；i++） ｛

GetElem（Lb，i，&e）;

If（！LocateElem（La，e，equal）） ListInsert（La，++La_len，e）; ｝ ｝

2. La，Lb中的数据元素按值非递减有序排列，现要求将La，Lb归并为一个新的线性表Lc，且Lc的数据元素仍为递减有序排列。 Void MergeList（List La，List Lb，List &Lc） ｛

InitList（Lc）； i=j=1； K=0；

La_len=ListLength（La）； Lb_len=ListLength（Lb）； While（（i<=La_len）&&（j<=Lb_len））｛//La，Lb均为非空 GetElem（La，i，&ai）; GetElem（Lb，j，&bj）;

if（ai<=bj）

｛ ListInsert（Lc，++k，ai）; ++i ； ｝ else

｛ ListInsert（Lc，++k，bj）; ++j ； ｝ ｝

While（i<=La_len）｛ GetElem（La，i++，ai）; While（j<=Lb_len）｛ GetElem（Lb，j++，bj）; ｝

3. 顺序表的存储结构静态描述：

#define ListSize 100 ；//定义表的空间为100 typedef int DataType ；//定义DataType类型为int型 typedef struct｛

DataType data[ListSize]；//用data存放表的结点 int length ； ｝Seqlist；

4. 顺序表的存储结构动态描述：

# define List_Init_Size 100；//线性表存储空间的初始化分配量 # define ListIncrement 10；//线性表存储空间的分配增量 typedef int Elemtype； （自己加上的语句） typedef struct｛

Elemtype *elem； //定义了一个指向ElemType类型的指针elem; int length；

int listsize；//当前分配的存储容量（以sizeof(ElemType)为单位） ｝SqList；

5. 线性表初始化或构造一个空的线性表 typedef int Status；

Status InitList_Sq（SqList &L）｛

L.elem=（ElemType *） malloc （List_Init_Size * sizeof（ElemType） ）； if（！L.elem） exit（VOERFLOW）；//存储分配失败

ListInsert（Lc，++k，ai）; ｝ ListInsert（Lc，++k，bj）; ｝

L.length=0； //空表长度为0 L.listsize=List_Init_size；//初始存储容量 Return OK； ｝//InitList_Sq

6. 获取元素值的算法。读取顺序线性表中第i个元素的取值。 States GetElem（List L，int i，Elemtype &e） ｛

if（i<0 || i>L.nlength） return ERROR； e=L.Elem[i-1]； return OK； ｝

7. 将新结点x插入L第i个结点ai的位置上（自考教材上的代码） Void InsertList（SeqList *L , DataType x , int i）｛

if(i<1||i>L->length+1) Error(“positon error”); //非法位置,退出运行 if(L->length>=ListSize) Error(“overflow”); //表空间溢出,退出运行 for(j=L->length-1;j>=i-1;j--)

L->data[j+1]=L->data[j]; //结点后移n-i+1

L->data[i-1]=x; //插入x L->length++; //表长加1 }

在顺序线性表L中的第i 个位置之前插入新的元素e ，i的合法值为1<=i<=ListLength_Sq（L）+1 Status ListInsert_Sq（SqList &L，int i ，ElemType e）｛

if（ i<=1 || i>L.length+1 ） return ERROR；

if（ L.length >=L.listsize）｛ //当前存储空间已满，增加分配

newbase=（ElemType *）realloc（L.elem，（L.listsize+ListIncrement） * sizeof（Elemtype））； if（！newbase ） exit（OVERFLOW）； //存储分配失败 L.elem=newbase； //新基址 L.listsize+=ListIncrement； //增加存储容量 ｝

q=&（L.elem[i-1]）； //q为插入位置

for（p=&（ L.elem[ L.length-1 ] ）; p>=q ; --p） *（p+1）=*P；//插入位置及之后的元素右移 *q=e； //插入e ++L.length ；//表长增1 return OK ；

｝//ListInsert_Sq

8. 在顺序线性表L中删除第i个元素，并用e返回其值 Status ListDelete_Sq（SqList &L， int i， Elemtype &e）｛ if（（i<1）||（i>L.length）） return ERROR； //i值不合法 p=&（L.elem[i-1]）； //p为被删除元素的位置 e=*p； //被删除元素的值赋给e q=L.elem+L.length-1； //b表尾元素的位置

for（++p ；p<=q；++p）*(p-1)=*(p)；//被删除元素之后的元素左移

--L.length； return OK ； ｝//ListDelete_Sq

从L所指定的顺序表中删除第i个结点ai （自考教材代码） Void DeleteList(SeqList *L, int i){

int j;

if(i<1||i>L->length)

Error(“positon error”); //非法位置 for(j=i; j<=L->length-1; j++)

L->data[j-1]=L->data[j]; //结点前移 n-i L->length--; //表长减1 }

9. 在顺序线性表中查找第1个值与e满足compare（）的元素的位序，若找到，则返回其在L中的位序，否则返回0. int LocatElem_Sq（SqList L， Elemtype e， Status（*compare）（ElemType，ElemType））｛ i=1；//i的初值为第一个元素的位序

p=L.elem；//p的初值为第一个元素的存储位置 while（i<=L.length && !（*compare）（*p++，e）） ++i；

if（i<=L.length） return i ； else return 0； ｝//LocateElem_Sq

10. 线性表的单链表存储结构 typedef struct LNode｛ ElemType data； struct LNode *next； ｝LNode，*LinkList；

11. GetElem在单链表中的实现，L为带头结点的单链表的头指针。当第i个元素存在时，其值赋给e并返回OK，否则返回ERROR Status GetElem_L（LinkList L，int i ；ElemType &e）｛ P=L->nest；j=1； //初始化，p指向第一个结点，j为计数器

While（ p && j < i ）｛ p=p->next；++j；｝ //顺指针向后查找，直到p指向第i个元素或p为空 if（ !p || j>i ） return ERROR； //第i个元素不存在 e=p->data； //取第i个元素 return OK ； ｝//GetElem_L

12. 在带头结点的单链表线性表L中第i个位置之前插入元素e Status ListInsert_L（LinkList &L， int i ， Elemtype e）

｛p=L；j=0；

while（p && jnext；++j；｝//寻找第i-1个结点 if（!p || j>i-1） reture ERROR；//i小于1或者大于表长加1 s=（LinkList）malloc（sizeof（LNode））； //生产新结点 s->data=e； s->next=p->next； p->next=s； return OK；

｝//ListInsert_L

13. 在带头结点的单链线性表L中，删除第i个元素，并由e返回其值

Status ListDelete_L（LinkList &L，int i，Elemtype &e） ｛P=L；j=0；

While（p->next &&jnext； ++j； ｝

if（!（p->next）|| j>i-1）return ERROR； //删除位置不合理

q=p->next；

p->next=q->next； //删除并释放结点 e=q->data； free（q）； return OK；

｝//ListDelete_L

14. 从表尾到表头逆向建立单链表的算法 Void CreateList_L（LinkList &L，int n；） ｛ L=（LinkList）malloc （sizeof（LNode））；

L->next=NULL； //先建立一个带头结点的单链表 for（i=n；i< ；--i）

p=（LinkList）malloc（sizeof（LNode））； //生成新结点 scanf（&p->data）；//输入元素值 p->next=L->next； //插入到表头 L->next=p；

｝// CreateList_L

15. La，Lb中的数据元素按值非递减有序排列，现要求将La，Lb归并为一个新的线性表Lc，且Lc的数据元素仍为递减有序排列。 Void MergeList_L（LinkList &La，LinkList &Lb，LinkList &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的头结点 ｝//MergeList_L

16. 线性表的静态单链表存储结构（这种链表是用数组描述的即静态单链表） # define MaxSize 1000 //链表的长度 typedef struct｛ Elemtype data; Int cur;

｝component , SLinkList[MxaSize]；

17. 在静态单链表中实现定位函数LocataElem。即查找第1个值为e的元素，若找到，则返回它在L中的位序，否则返回0. int LocateElem_SL（SLinkList S ， ElemType e）｛ i=s[0].cur； //i指示表中的第一个结点

while（i && S[i].data!=e） i=S[i].cur； //在表中顺链查找 return i ； ｝//LocateElem_SL

18. 将整个数组空间初始化成为一个链表。（将一维数组space中个分量链成一个备用链表，space[0].cur为头指针，“0”表示空指针） void InitSpace_SL（SLinkList &space）｛

for（i=0；i< MaxSize-1； ++i） space[i].cur=i+1； space[MaxSize-1].cur=0；

｝//InitSpace_SL

19. 从备用空间取得一个结点。（若备用空间链表非空，则返回分配的结点下标，否则返回0） int Malloc_SL（SLinkList &space）｛

i=space[0].cur； if（space[0]cur）

space[0].cur=space[i].cur； return i ；

｝// Malloc_SL

20. 将空闲结点链结到备用链表上。（将下标为K的空间结点回收到备用链表） void Free_SL（SLinkList &space， int k）｛

space[k].cur=space[0].cur； space[0].cur=k；

｝// Free_SL

21. 依次输入集合A和B的元素，在一维数组space中建立表示集合（A-B）U（B-A）的静态链表，S为其头指针。假设备用空间足够大，

space[0].cur为其头指针。

void difference（SLinkList &space，int &S）｛

InitSpace_SL（space）； //初始化备用空间 S=Malloc_SL（sqace）； //生成S的头结点 r=S； //r指向S的当前最后结点

scanf（m，n）； //输入A和B的元素个数 for（j=1；j<=m；++j）｛ //建立集合A的链表

i=Malloc_SL（space）; //分配结点 scanf（space[i].data）； //输入A的元素值 space[r].cur=i；r=i； //插入到表尾 ｝//for

Space[r].cur=0； //尾结点的指针为空

for（j=1；j<=n；++j）｛ //依次输入B的元素，若不在当前表中，则插入，否则删除

scanf（b）；p=S；k=space[S].cur； //k指向集合A中的第一个结点 while（k!=space[r].cur && space[k].data!=b）｛//在当前表中查找

p=k；k=space[k].cur； ｝//while

if（k==space[r].cur）｛ //当前表中不存在该元素，插入在r所指结点之后，且r的位置不变

i=Malloc_SL（space）； space[i].data=b；

space[i].cur= space[r].cur； space[r]=i； ｝//if

else｛ //该元素已在表中，删除之

space[p].cur= space[k].cur； Free_SL（space，k）；

if（r==k） r=p； //若删除的是r所指结点，则需修改尾指针 ｝//else

｝//for ｝

22. 线性表的双向链表存储结构 Typedef struct DuLNode｛ ElemType data； struct DuLNode *prior； struct DuLNode *next；

｝DuLNode，*DuLinkList；

23. 在带头结点的双链循环线性表L中第i个位置之前插入元素e，i的合法值为1<=i<=表长+1. Statue ListInsert_DuL（DuLinkList &L，int i，ElemType e）｛ if（!（p=GetElemP_DuL（L，i））） //在L中确定插入位置 return ERROR； //p=NULL，即插入位置不合法 if（!（s=（DuLinkList）molloc（sizeof（DuLNode）））） return ERROR； s->data=e； s->prior=p->prior; p->prior->next=s; s->next=p; p->prior=s; ruturn OK; ｝//ListInert_DuL

24. 删除带头结点的双链循环线性表L的第i个元素，i的合法值为1<=i<=表长 Status ListDelete_DuL（DuLinkList &L，int i，ElemType &e）{

if（！（p=GetELemP_DuL（L，i）））//在L中确定第i个元素的位置指针p ruturn ERROR; //p=NULL，即第i个元素不存在 e=p->data;

p->prior->next=p->next; p->next->prior=p->prior; free（p）; return OK; }//ListDelete_DuL

本文来源：https://www.bwwdw.com/article/5pgh.html