《數(shù)據(jù)結(jié)構(gòu)》第一次上機(jī)測試代碼部分(最新版)

1、第一次數(shù)據(jù)結(jié)構(gòu)上機(jī)測試代碼題目分配： 本次測試一共三個(gè)大題目，包括A）順序表的基本操作，B）單鏈表的基本操作及C）棧和隊(duì)列的操作。1、 題目一有3個(gè)小題目，每位同學(xué)只需做其中一題即可，做題序號(hào)由學(xué)號(hào)后兩位模3決定。若模出來結(jié)果為1，則做第1道；結(jié)果為2，則做第2道；結(jié)果為0，做第3道。2、題目二也有3個(gè)小題目，每位同學(xué)只需做其中一題即可，做題序號(hào)同題目一。3、題目三所有同學(xué)都做。該題目有2個(gè)測試用例，測試用例由學(xué)號(hào)后一位模2決定。若模出來結(jié)果為1，則用第1個(gè)測試用例；結(jié)果為0，則用第2個(gè)測試用例。注意事項(xiàng)：1、 每個(gè)同學(xué)在D：盤下新建一個(gè)文件夾，以“班級(jí)+學(xué)號(hào)+姓名”形式命名，如：2班2012

2、0102張三。該文件夾中應(yīng)該包含三個(gè)子文件夾，包括了所有作業(yè)。2、 三個(gè)子文件夾分別對應(yīng)三個(gè)試題，分別命名為：1）順序表、2）鏈表、及3）棧和隊(duì)列。將相應(yīng)題目的工程建于各文件夾下。（也即，順序表文件夾應(yīng)該有順序表的操作的工程文件）3、 考試結(jié)束，請各位同學(xué)在座位上，等待監(jiān)考老師確認(rèn)你的考題之后方可簽字離開。第一部分 線性表題目一：*頭文件sequential.h*#ifndef _FUNC_H#define _FUNC_H/函數(shù)結(jié)果狀態(tài)代碼#define TRUE1#define FALSE0#define OK1#define ERROR0#define INFEASIBLE-1#defin

3、e OVERFLOW -2#define LIST_INIT_SIZE 100#define LISTINCREMENT 10typedef int Status;/Status是函數(shù)的類型，其值是函數(shù)結(jié)果狀態(tài)代碼typedef int ElemType;/數(shù)據(jù)元素的類型ElemType為inttypedef struct ElemType * elem;int length;int listsize;SqList;extern Status InitList_sq (SqList &L);/初始化一個(gè)空的順序表Lextern Status BuildList_sq (SqList &

4、amp;L, int n);/構(gòu)造由n個(gè)元素構(gòu)成的順序表Lextern Status ListInsert_sq (SqList &L, int i, ElemType e);/在順序表L中第i個(gè)位置插入新元素e,插入成功，返回1(OK)，否則返回0(ERROR)extern Status ListDelete_sq (SqList &L, int i, ElemType &e);/在順序線性表L中刪除第i個(gè)元素,并用e返回其值，刪除成功，返回1(OK)，否則返回0(ERROR)extern Status LocateElem_sq (SqList &L,Ele

5、mType e); /定位元素e，定位成功，函數(shù)返回該元素在順序表中的位置，否則返回0extern Status ClearList_sq(SqList &L); /清空順序表extern Status ListTraverse_sq (SqList L);/遍歷順序表extern void menu();/選擇菜單#endif*功能函數(shù) function.cpp*#include <stdlib.h>#include "stdio.h"#include "sequential.h"Status InitList_sq (SqList

6、 &L)/初始化一個(gè)空的順序表LL.elem = (ElemType *)malloc(LIST_INIT_SIZE * sizeof(ElemType);if (! L.elem) return ERROR;L.length = 0;L.listsize = LIST_INIT_SIZE;return OK;/end of InitListStatus BuildList_sq(SqList &L, int n)/構(gòu)造由n個(gè)元素構(gòu)成的順序表Lif (L.length >= L.listsize)ElemType * newbase = (ElemType *)reall

7、oc(L.elem,(L.listsize + LISTINCREMENT) * sizeof(ElemType);if (!newbase) return ERROR;L.elem = newbase;L.listsize += LISTINCREMENT;ElemType e;for (int i = 0; i<n; i+)printf("第%d個(gè)元素的值為:",i+1);scanf("%d", &e);L.elemi=e;return OK;/依次訪問L中的每個(gè)數(shù)據(jù)元素并輸出其值Status ListTraverse_sq (SqLi

8、st L)int i = 0;if (! L.elem) return ERROR;while (i < L.length)printf("%d ", L.elemi);i+;printf("n");return OK;Status ClearList_sq(SqList &L)/清空順序表if (! L.elem) return ERROR;L.elem = NULL;L.length = 0;L.listsize = 0;return OK;Status ListInsert_sq (SqList &L, int i, Elem

9、Type e)/在順序表L中第i個(gè)位置插入新元素e,插入成功，返回1(OK)，否則返回0(ERROR)return OK;/end of ListInsertStatus ListDelete_sq (SqList &L, int i, ElemType &e)/在順序線性表L中刪除第i個(gè)元素,并用e返回其值，刪除成功，返回1(OK)，否則返回0(ERROR)return OK;Status LocateElem_sq(SqList &L, ElemType e) /定位元素e，定位成功，函數(shù)返回該元素在順序表中的位置，否則返回0return 0; /打印菜單void

10、menu()printf("n請選擇操所n");printf("1.插入元素n");printf("2.刪除元素n");printf("3.定位元素n"); printf("4.遍歷順序表n");printf("0.清空線性表,并退出n");*主函數(shù)sequential.cpp*#include <stdio.h>#include "sequential.h"void main()SqList L;int i=0;ElemType e = 0;

11、if (!InitList_sq(L) printf("建立空線性表失敗,請重啟程序n");elseprintf("請輸入需要建立的元素個(gè)數(shù),輸入0表示退出n");scanf("%d", &L.length);printf("請逐個(gè)輸入整數(shù)型元素:n");if (!BuildList_sq(L, L.length) printf("建立線性表失敗,請重新輸入n");elsechar choice = 1;while(choice) menu();scanf("%d",

12、 &choice);switch(choice)case 1:break;case 2:break;case 3:break;case 4:ListTraverse_sq(L);break;/end of switch /end of while/end of buildlist/end of initlist 題目二：* 頭文件linked .h*#ifndef _FUNC_H#define _FUNC_H/函數(shù)結(jié)果狀態(tài)代碼#define TRUE1#define FALSE0#define OK1#define ERROR0#define INFEASIBLE-1#define O

13、VERFLOW -2#define LIST_INIT_SIZE 100#define LISTINCREMENT 10/Status是函數(shù)的類型，其值是函數(shù)結(jié)果狀態(tài)代碼typedef int Status;typedef int ElemType;typedef struct LNode ElemType data; / 數(shù)據(jù)域 struct LNode *next; / 指針域 LNode, *LinkList; extern Status ListInsert_L(LinkList L, int i, ElemType e);/向鏈表的i位置中插入元素e,如果插入成功，函數(shù)返回1，否則返

14、回0：extern Status ListDelete_L(LinkList L, int i, ElemType &e);/刪除鏈表i位置元素，并用e返回,如果刪除成功，函數(shù)返回1，否則返回0：extern Status LocateElem(LinkList L,ElemType e);/定位元素e在鏈表中的位置,存在返回該元素的位序，否則返回0；extern void ClearList(LinkList &L);/清空鏈表extern void CreateListe_L(LinkList &L,int n );/創(chuàng)建鏈表extern Status ListTr

15、avel_L(LinkList L);/遍歷鏈表extern void menu();/菜單#endif*功能函數(shù) function.cpp*#include <stdlib.h>#include "stdio.h"#include "linked .h"void CreateListe_L(LinkList &L,int n ) /生成鏈表 L=(LinkList)malloc(sizeof(LNode); L->next=NULL; LinkList q=L; for (int i=1;i<=n;i+) LinkLis

16、t p=(LinkList)malloc(sizeof(LNode); scanf("%d",&p->data); q->next=p; q=p; q->next=NULL; Status ListTravel_L(LinkList L)/遍歷鏈表LinkList p;if (!L) return ERROR;printf("鏈表為:");p=L->next;while (p)printf("%d ",p->data);p=p->next;return OK;void ClearList(L

17、inkList &L) /清除鏈表 while ( L->next) LinkList p=L->next; L->next = p->next; free(p); Status ListInsert_L(LinkList L, int i, ElemType e) /向鏈表的i位置中插入元素e,如果插入成功，函數(shù)返回1，否則返回0 return OK;/end of ListInsertStatus ListDelete_L(LinkList L, int i, ElemType &e) /刪除鏈表i位置元素，并用e返回,如果刪除成功，函數(shù)返回1，否則

18、返回0 return OK; Status LocateElem(LinkList L,ElemType e)/定位元素e在鏈表中的位置,存在返回該元素的位序，否則返回0 return OK;void menu()/菜單printf("n*n");printf("1.插入元素n");printf("2.刪除元素n");printf("3.定位元素n");printf("4.遍歷鏈表n");printf("0.清空鏈表,并退出n");printf("n*n"

19、);*主函數(shù)linked .cpp*#include <stdio.h>#include <stdlib.h>#include " linked.h"void main()LinkList L=(LinkList)malloc(sizeof (LNode);L->next = NULL;int i;int n;ElemType e = 0;char choice = 1;printf("請輸入要建立的鏈表元素個(gè)數(shù):");scanf("%d", &n);CreateListe_L(L, n);whi

20、le(choice) menu();scanf("%d", &choice);switch(choice)case 1:break;case 2:break;case 3:break;case 4:break;/end of switch /end of while題目三：*頭文件3.h*#ifndef _FUNC_H#define _FUNC_H#define STACK_SIZE 3 /順序棧的深度為3typedef char SElemType;/棧元素的類型為chartypedef struct SElemType *base; SElemType *top

21、; int stacksize; SqStack;/順序棧 extern int InitStack (SqStack &s);/構(gòu)造棧extern int POP (SqStack &s, SElemType &e);/S棧頂元素出棧，賦給變量e；extern int PUSH (SqStack &s, SElemType e);/元素e入S棧；extern int StackEmpty(SqStack s);/判S棧是否為空extern int EnQueue(SqStack &S1, SqStack &S2,SElemType x);/利用

22、兩量棧S1,S2實(shí)現(xiàn)元素x的入對列extern int QueueEmpty(SqStack S1,SqStack S2);/判隊(duì)列是否為空算法extern int DeQueue(SqStack &S2,SqStack &S1,SElemType &x);/利用兩量棧S1,S2實(shí)現(xiàn)元素x的出對列,成功返回1，否則返回0extern void menu();/菜單extern void TravelQueue(SqStack S1, SqStack S2);/遍歷隊(duì)列#endif*功能函數(shù)function.h*#include <stdio.h>#inclu

23、de <stdlib.h>#include "3.h"int InitStack (SqStack &s)/初始化順序棧ss.base=(SElemType*)malloc(STACK_SIZE * sizeof (SElemType);if (!s.base) return 0; /存儲(chǔ)分配失敗s.top = s.base;s.stacksize = STACK_SIZE;return 1;int POP (SqStack &s, SElemType &e) /出棧操作，并用e返回棧頂 if (s.top = s.base) retur

24、n 0;/ 若?？眨祷谽RROR e = *-s.top; /不空，用形參e返回其值 return 1;/返回OK；int PUSH (SqStack &s, SElemType e) / 入棧操作if (s.top - s.base >= s.stacksize) return 0; /棧滿，返回ERROR *s.top+ = e; /*S.top=e;S.top+; return 1;int StackEmpty(SqStack s)/判斷棧S是否為空，為空，返回OK，否則返回ERRORif (s.base = s.top) return 1;return 0;void m

25、enu()/菜單printf("n*n");printf("1:入隊(duì)列n");printf("2:出隊(duì)列n"); printf("3:判空n");printf("4:遍歷n");printf("0.退出n");printf("n*n");/遍歷隊(duì)列void TravelQueue(SqStack S1, SqStack S2) SElemType *p_S1, *p_S2; printf("隊(duì)列中的元素為：n"); for( p_S2=

26、S2.top-1; p_S2>=S2.base; p_S2-) printf("%c-",*p_S2);for(p_S1=S1.base ; p_S1<S1.top ; p_S1+) printf("%c-",*p_S1);/利用兩量棧S1,S2實(shí)現(xiàn)元素x的入對列int EnQueue(SqStack &S1, SqStack &S2,SElemType x)/將x入隊(duì)列，若入隊(duì)列成功返回1,否則返回0。SElemType x1;if(S1.top - S1.base >= S1.stacksize && !StackEmpty(S2) /S1滿S2非空