华南农业大学数据结构OJ题目(不含答案).doc

Description 编写算法，创建初始化容量为LIST_INIT_SIZE的顺序表T，并实现插入、删除、遍历操作。本题目给出部分代码，请补全内容。#include#include#define OK 1 #define ERROR 0#define LIST_INIT_SIZE 100#define LISTINCREMENT 10#define ElemType inttypedef structint *elem;int length;int listsize;SqList;int InitList_Sq(SqList &L)/ 算法2.3，构造一个空的线性表L，该线性表预定义大小为LIST_INIT_SIZE/ 请补全代码int Load_Sq(SqList &L)/ 输出顺序表中的所有元素int i;if(_) printf(The List is empty!); / 请填空elseprintf(The List is: );for(_) printf(%d ,_); / 请填空printf(n);return OK;int ListInsert_Sq(SqList &L,int i,int e)/ 算法2.4，在顺序线性表L中第i个位置之前插入新的元素e/ i的合法值为1iL.length +1/ 请补全代码int ListDelete_Sq(SqList &L,int i, int &e)/ 算法2.5,在顺序线性表L中删除第i个位置的元素，并用e返回其值/ i的合法值为1iL.length/ 请补全代码int main()SqList T;int a, i;ElemType e, x;if(_) / 判断顺序表是否创建成功printf(A Sequence List Has Created.n);while(1)printf(1:Insert elementn2:Delete elementn3:Load all elementsn0:ExitnPlease choose:n);scanf(%d,&a);switch(a)case 1: scanf(%d%d,&i,&x);if(_) printf(Insert Error!n); / 判断i值是否合法，请填空else printf(The Element %d is Successfully Inserted!n, x); break;case 2: scanf(%d,&i);if(_) printf(Delete Error!n); / 判断i值是否合法，请填空else printf(The Element %d is Successfully Deleted!n, e);break;case 3: Load_Sq(T);break;case 0: return 1;输入格式测试样例格式说明：根据菜单操作：1、输入1，表示要实现插入操作，紧跟着要输入插入的位置和元素，用空格分开2、输入2，表示要实现删除操作，紧跟着要输入删除的位置3、输入3，表示要输出顺序表的所有元素4、输入0，表示程序结束输入样例11 211 32130输出样例A Sequence List Has Created.1:Insert element2:Delete element3:Load all elements0:ExitPlease choose:The Element 2 is Successfully Inserted!1:Insert element2:Delete element3:Load all elements0:ExitPlease choose:The Element 3 is Successfully Inserted!1:Insert element2:Delete element3:Load all elements0:ExitPlease choose:The Element 3 is Successfully Deleted!1:Insert element2:Delete element3:Load all elements0:ExitPlease choose:The List is: 2 1:Insert element2:Delete element3:Load all elements0:ExitPlease choose:顺序表的基本操作代码如下：#include#include#define OK 1#define ERROR 0#define LIST_INIT_SIZE 100#define LISTINCREMENT 10#define ElemType inttypedef int Status;typedef struct int *elem; int length; int listsize;SqList;Status InitList_Sq(SqList &L) / 算法2.3 / 构造一个空的线性表L。 L.elem = (ElemType *)malloc(LIST_INIT_SIZE*sizeof(ElemType); if (!L.elem) return OK; / 存储分配失败 L.length = 0; / 空表长度为0 L.listsize = LIST_INIT_SIZE; / 初始存储容量 return OK; / InitList_SqStatus ListInsert_Sq(SqList &L, int i, ElemType e) / 算法2.4 / 在顺序线性表L的第i个元素之前插入新的元素e， / i的合法值为1iListLength_Sq(L)+1 ElemType *p; if (i L.length+1) return ERROR; / i值不合法 if (L.length = L.listsize) / 当前存储空间已满，增加容量 ElemType *newbase = (ElemType *)realloc(L.elem, (L.listsize+LISTINCREMENT)*sizeof (ElemType); if (!newbase) return ERROR; / 存储分配失败 L.elem = newbase; / 新基址 L.listsize += LISTINCREMENT; / 增加存储容量 ElemType *q = &(L.elemi-1); / q为插入位置 for (p = &(L.elemL.length-1); p=q; -p) *(p+1) = *p; / 插入位置及之后的元素右移 *q = e; / 插入e +L.length; / 表长增1 return OK; / ListInsert_SqStatus ListDelete_Sq(SqList &L, int i, ElemType &e) / 算法2.5 / 在顺序线性表L中删除第i个元素，并用e返回其值。 / i的合法值为1iListLength_Sq(L)。 ElemType *p, *q; if (iL.length) return ERROR; / i值不合法 p = &(L.elemi-1); / p为被删除元素的位置 e = *p; / 被删除元素的值赋给e q = L.elem+L.length-1; / 表尾元素的位置 for (+p; p=q; +p) *(p-1) = *p; / 被删除元素之后的元素左移 -L.length; / 表长减1 return OK; / ListDelete_Sq编写算法，将两个非递减有序顺序表A和B合并成一个新的非递减有序顺序表C。输入格式第一行：顺序表A的元素个数第二行：顺序表A的各元素（非递减），用空格分开第三行：顺序表B的元素个数第四行：顺序表B的各元素（非递减），用空格分开输出格式第一行：顺序表A的元素列表第二行：顺序表B的元素列表第三行：合并后顺序表C的元素列表输入样例51 3 5 7 952 4 6 8 10输出样例List A:1 3 5 7 9 List B:2 4 6 8 10 List C:1 2 3 4 5 6 7 8 9 10顺序表的基本操作代码如下：#include#include#define OK 1#define ERROR 0#define LIST_INIT_SIZE 100#define LISTINCREMENT 10#define ElemType inttypedef int Status;typedef struct int *elem; int length; int listsize;SqList;Status InitList_Sq(SqList &L) / 算法2.3 / 构造一个空的线性表L。 L.elem = (ElemType *)malloc(LIST_INIT_SIZE*sizeof(ElemType); if (!L.elem) return OK; / 存储分配失败 L.length = 0; / 空表长度为0 L.listsize = LIST_INIT_SIZE; / 初始存储容量 return OK; / InitList_SqStatus ListInsert_Sq(SqList &L, int i, ElemType e) / 算法2.4 / 在顺序线性表L的第i个元素之前插入新的元素e， / i的合法值为1iListLength_Sq(L)+1 ElemType *p; if (i L.length+1) return ERROR; / i值不合法 if (L.length = L.listsize) / 当前存储空间已满，增加容量 ElemType *newbase = (ElemType *)realloc(L.elem, (L.listsize+LISTINCREMENT)*sizeof (ElemType); if (!newbase) return ERROR; / 存储分配失败 L.elem = newbase; / 新基址 L.listsize += LISTINCREMENT; / 增加存储容量 ElemType *q = &(L.elemi-1); / q为插入位置 for (p = &(L.elemL.length-1); p=q; -p) *(p+1) = *p; / 插入位置及之后的元素右移 *q = e; / 插入e +L.length; / 表长增1 return OK; / ListInsert_SqStatus ListDelete_Sq(SqList &L, int i, ElemType &e) / 算法2.5 / 在顺序线性表L中删除第i个元素，并用e返回其值。 / i的合法值为1iListLength_Sq(L)。 ElemType *p, *q; if (iL.length) return ERROR; / i值不合法 p = &(L.elemi-1); / p为被删除元素的位置 e = *p; / 被删除元素的值赋给e q = L.elem+L.length-1; / 表尾元素的位置 for (+p; p=q; +p) *(p-1) = *p; / 被删除元素之后的元素左移 -L.length; / 表长减1 return OK; / ListDelete_Sq设有一顺序表A=（a0,a1,., ai,.an-1)，其逆顺序表定义为A=( an-1,., ai,.,a1, a0)。设计一个算法，将顺序表逆置，要求顺序表仍占用原顺序表的空间。输入格式第一行：输入顺序表的元素个数第二行：输入顺序表的各元素，用空格分开输出格式第一行：逆置前的顺序表元素列表第二行：逆置后的顺序表元素列表输入样例101 2 3 4 5 6 7 8 9 10输出样例The List is:1 2 3 4 5 6 7 8 9 10 The turned List is:10 9 8 7 6 5 4 3 2 1Description 编写算法，创建一个含有n个元素的带头结点的单链表L并实现插入、删除、遍历操作。本题目提供部分代码，请补全内容。#include#include#define ERROR 0#define OK 1 #define ElemType inttypedef struct LNode int data; struct LNode *next;LNode,*LinkList;int CreateLink_L(LinkList &L,int n)/ 创建含有n个元素的单链表 LinkList p,q; int i; ElemType e; L = (LinkList)malloc(sizeof(LNode); L-next = NULL; / 先建立一个带头结点的单链表 q = (LinkList)malloc(sizeof(LNode); q = L; for (i=0; inext; if(_)printf(The List is empty!); / 请填空 else printf(The LinkList is:); while(_) / 请填空 printf(%d ,p-data); _ / 请填空 printf(n); return OK;int LinkInsert_L(LinkList &L,int i,ElemType e)/ 算法2.9/ 在带头结点的单链线性表L中第i个位置之前插入元素e/ 请补全代码int LinkDelete_L(LinkList &L,int i, ElemType &e)/ 算法2.10/ 在带头结点的单链线性表L中，删除第i个元素，并用e返回其值/ 请补全代码int main() LinkList T; int a,n,i; ElemType x, e; printf(Please input the init size of the linklist:n); scanf(%d,&n); printf(Please input the %d element of the linklist:n, n); if(_) / 判断链表是否创建成功，请填空 printf(A Link List Has Created.n); LoadLink_L(T); while(1)printf(1:Insert elementn2:Delete elementn3:Load all elementsn0:ExitnPlease choose:n);scanf(%d,&a);switch(a)case 1: scanf(%d%d,&i,&x); if(_) printf(Insert Error!n); / 判断i值是否合法，请填空 else printf(The Element %d is Successfully Inserted!n, x); break;case 2: scanf(%d,&i); if(_) printf(Delete Error!n); / 判断i值是否合法，请填空 else printf(The Element %d is Successfully Deleted!n, e); break;case 3: LoadLink_L(T); break;case 0: return 1;输入格式测试样例格式说明：根据菜单操作：1、输入1，表示要实现插入操作，紧跟着要输入插入的位置和元素，用空格分开2、输入2，表示要实现删除操作，紧跟着要输入删除的位置3、输入3，表示要输出顺序表的所有元素4、输入0，表示程序结束输入样例33 6 9314 122130输出样例Please input the init size of the linklist:Please input the 3 element of the linklist:A Link List Has Created.The LinkList is:3 6 9 1:Insert element2:Delete element3:Load all elements0:ExitPlease choose:The LinkList is:3 6 9 1:Insert element2:Delete element3:Load all elements0:ExitPlease choose:The Element 12 is Successfully Inserted!1:Insert element2:Delete element3:Load all elements0:ExitPlease choose:The Element 3 is Successfully Deleted!1:Insert element2:Delete element3:Load all elements0:ExitPlease choose:The LinkList is:6 9 12 1:Insert element2:Delete element3:Load all elements0:ExitPlease choose:线性链表的基本操作如下：#include#include#define ERROR 0#define OK 1 #define ElemType inttypedef int Status;typedef struct LNode int data; struct LNode *next;LNode,*LinkList;Status ListInsert_L(LinkList &L, int i, ElemType e) / 算法2.9 / 在带头结点的单链线性表L的第i个元素之前插入元素e LinkList p,s; p = L; int j = 0; while (p & j next; +j; if (!p | j i-1) return ERROR; / i小于1或者大于表长 s = (LinkList)malloc(sizeof(LNode); / 生成新结点 s-data = e; s-next = p-next; / 插入L中 p-next = s; return OK; / LinstInsert_LStatus ListDelete_L(LinkList &L, int i, ElemType &e) / 算法2.10 / 在带头结点的单链线性表L中，删除第i个元素，并由e返回其值 LinkList p,q; p = L; int j = 0; while (p-next & j next; +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设计一个算法将两个非递减有序链表A和B合并成一个新的非递减有序链表C。输入格式第一行：单链表A的元素个数第二行：单链表A的各元素（非递减），用空格分开第三行：单链表B的元素个数第四行：单链表B的各元素（非递减），用空格分开输出格式第一行：单链表A的元素列表第二行：单链表B的元素列表第三行：合并后单链表C的元素列表输入样例612 24 45 62 84 96415 31 75 86输出样例List A:12 24 45 62 84 96 List B:15 31 75 86 List C:12 15 24 31 45 62 75 84 86 96线性链表的基本操作如下：#include#include#define ERROR 0#define OK 1 #define ElemType inttypedef int Status;typedef struct LNode int data; struct LNode *next;LNode,*LinkList;Status ListInsert_L(LinkList &L, int i, ElemType e) / 算法2.9 / 在带头结点的单链线性表L的第i个元素之前插入元素e LinkList p,s; p = L; int j = 0; while (p & j next; +j; if (!p | j i-1) return ERROR; / i小于1或者大于表长 s = (LinkList)malloc(sizeof(LNode); / 生成新结点 s-data = e; s-next = p-next; / 插入L中 p-next = s; return OK; / LinstInsert_LStatus ListDelete_L(LinkList &L, int i, ElemType &e) / 算法2.10 / 在带头结点的单链线性表L中，删除第i个元素，并由e返回其值 LinkList p,q; p = L; int j = 0; while (p-next & j next; +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设有一线性表A=（a0,a1,., ai,.an-1)，其逆线性表定义为A=( an-1,., ai,.,a1, a0)，设计一个算法，将线性表逆置，要求线性表仍占用原线性表的空间。输入格式第一行：输入n，表示单链表的元素个数第二行：输入单链表的各元素，用空格分开输出格式第一行：输出单链表逆置前的元素列表第二行：输出单链表逆置后的元素列表输入样例832 97 54 65 35 84 61 75输出样例The List is:32 97 54 65 35 84 61 75 The turned List is:75 61 84 35 65 54 97 32#include #include #define OK 1#define ERROR 0#define STACK_INIT_SIZE 100 / 存储空间初始分配量#define STACKINCREMENT 10 / 存储空间分配增量typedef int SElemType; / 定义栈元素类型typedef int Status; / Status是函数的类型,其值是函数结果状态代码，如OK等struct SqStack SElemType *base; / 在栈构造之前和销毁之后，base的值为NULL SElemType *top; / 栈顶指针 int stacksize; / 当前已分配的存储空间，以元素为单位; / 顺序栈Status InitStack(SqStack &S) / 构造一个空栈S，该栈预定义大小为STACK_INIT_SIZE/ 请补全代码Status Push(SqStack &S,SElemType e) / 在栈S中插入元素e为新的栈顶元素/ 请补全代码Status Pop(SqStack &S,SElemType &e) / 若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR/ 请补全代码Status GetTop(SqStack S,SElemType &e) / 若栈不空，则用e返回S的栈顶元素，并返回OK；否则返回ERROR/ 请补全代码int StackLength(SqStack S) / 返回栈S的元素个数/ 请补全代码Status StackTraverse(SqStack S)/ 从栈顶到栈底依次输出栈中的每个元素SElemType *p = (SElemType *)malloc(sizeof(SElemType); p = _ /请填空if(_)printf(The Stack is Empty!); /请填空elseprintf(The Stack is: );p-;while(_) /请填空printf(%d , *p);_ /请填空printf(n);return OK;int main() int a; SqStack S;SElemType x, e; if(_) / 判断顺序表是否创建成功，请填空printf(A Stack Has Created.n);while(1) printf(1:Push n2:Pop n3:Get the Top n4:Return the Length of the Stackn5:Load the Stackn0:ExitnPlease choose:n);scanf(%d,&a);switch(a)case 1: scanf(%d, &x); if(_) printf(Push Error!n); / 判断Push是否合法，请填空 else printf(The Element %d is Successfully Pushed!n, x); break;case 2: if(_) printf(Pop Error!n); / 判断Pop是否合法，请填空 else printf(The Element %d is Successfully Poped!n, e); break;case 3: if(_)printf(Get Top Error!n); / 判断Get Top是否合法，请填空 else printf(The Top Element is %d!n, e); break;case 4: printf(The Length of the Stack is %d!n,_); /请填空 break;case 5: _ /请填空 break;case 0: return 1;输入格式测试样例格式说明：根据菜单操作：1、输入1，表示要实现Push操作，紧跟着输入要Push的元素2、输入2，表示要实现Pop操作3、输入3，返回栈顶元素4、输入4，返回栈的元素个数5、输入5，表示从栈顶到栈底输出栈的所有元素6、输入0，表示程序结束输入样例121416534252220输出样例A Stack Has Created.1:Push 2:Pop 3:Get the Top 4:Return the Length of the Stack5:Load the Stack0:ExitPlease choose:The Element 2 is Successfully Pushed!1:Push 2:Pop 3:Get the Top 4:Return the Length of the Stack5:Load the Stack0:ExitPlease choose:The Element 4 is Successfully Pushed!1:Push 2:Pop 3:Get the Top 4:Return the Length of the Stack5:Load the Stack0:ExitPlease choose:The Element 6 is Successfully Pushed!1:Push 2:Pop 3:Get the Top 4:Return the Length of the Stack5:Load the Stack0:ExitPlease choose:The Stack is: 6 4 2 1:Push 2:Pop 3:Get the Top 4:Return the Length of the Stack5:Load the Stack0:ExitPlease choose:The Top Element is 6!1:Push 2:Pop 3:Get the Top 4:Return the Length of the Stack5:Load the Stack0:ExitPlease choose:The Length of the Stack is 3!1:Push 2:Pop 3:Get the Top 4:Return the Length of the Stack5:Load the Stack0:ExitPlease choose:The Element 6 is Successfully Poped!1:Push 2:Pop 3:Get the Top 4:Return the Length of the Stack5:Load the Stack0:ExitPlease choose:The Stack is: 4 2 1:Push 2:Pop 3:Get the Top 4:Return the Length of the Stack5:Load the Stack0:ExitPlease choose:The Element 4 is Successfully Poped!1:Push 2:Pop 3:Get the Top 4:Return the Length of the Stack5:Load the Stack0:ExitPlease choose:The Element 2 is Successfully Poped!1:Push 2:Pop 3:Get the Top 4:Return the Length of the Stack5:Load the Stack0:ExitPlease choose:Pop Error!1:Push 2:Pop 3:Get the Top 4:Return the Length of the Stack5:Load the Stack0:ExitPlease choose:Description 创建一个空的循环队列，并实现入队、出队、返回队列的长度、返回队头元素、队列的遍历等基本算法。请将下面的程序补充完整。#include #include #define OK 1#define ERROR 0typedef int Status; / Status是函数的类型,其值是函数结果状态代码，如OK等typedef int QElemType;#define MAXQSIZE 100 / 最大队列长度(对于循环队列，最大队列长度要减1)typedef struct QElemType *base; / 初始化的动态分配存储空间 int front; / 头指针,若队列不空,指向队列头元素 int rear; / 尾指针,若队列不空,指向队列尾元素的下一个位置 SqQueue;Status InitQueue(SqQueue &Q) / 构造一个空队列Q，该队列预定义大小为MAXQSIZE/ 请补全代码Status EnQueue(SqQueue &Q,QElemType e) / 插入元素e为Q的新的队尾元素/ 请补全代码Status DeQueue(SqQueue &Q, QElemType &e) / 若队列不空, 则删除Q的队头元素, 用e返回其值, 并返回OK; 否则返回ERROR/ 请补全代码Status GetHead(SqQueue Q, QElemType &e)/ 若队列不空，则用e返回队头元素，并返回OK，否则返回ERROR/ 请补全代码int QueueLength(SqQueue Q) / 返回Q的元素个数/ 请补全代码Status QueueTraverse(SqQueue Q) / 若队列不空，则从队头到队尾依次输出各个队列元素，并返回OK；否则返回ERROR.int i;i=Q.front;if(_)printf(The Queue is Empty!); /请填空elseprintf(The Queue is: );while(_) /请填空printf(%d ,_ ); /请填空i = _; /请填空printf(n);return OK;int main()int a; SqQueue S;QElemType x, e; if(_) / 判断顺序表是否创建成功，请填空printf(A Qu