重 慶 大 學(xué)基礎(chǔ)性實踐環(huán)節(jié)(數(shù)據(jù)結(jié)構(gòu))實踐報告實踐課程名稱 數(shù)據(jù)結(jié)構(gòu)與算法 開課 實 驗 室 數(shù)學(xué)實驗教學(xué)中心 學(xué) 院 數(shù)學(xué)與統(tǒng)計學(xué)院年 級 2009級 專 業(yè) 班 信息與計算科學(xué)01班學(xué) 生 姓 名 學(xué) 號 20092250 開 課 時 間 2011 至 2012 學(xué)年 第 一 學(xué)期總 成 績教師簽名實驗一、單鏈表的基本操作一、實驗?zāi)康?、掌握線性鏈表的操作特點，即指針是邏輯關(guān)系的映像2、掌握動態(tài)產(chǎn)生單鏈表的方法3、熟練掌握單鏈表的插入、刪除操作特點，即指針賦值的先后次序二、實驗內(nèi)容1、動態(tài)創(chuàng)建單鏈表2、實現(xiàn)線性表鏈?zhǔn)酱鎯Y(jié)構(gòu)中元素的插入3、實現(xiàn)線性表鏈?zhǔn)酱鎯Y(jié)構(gòu)中元素的刪除三、具體要求1、單鏈表的存儲結(jié)構(gòu)定義typedef struct LNode { ElemType data; // 數(shù)據(jù)域 struct LNode *next; // 指針域 } LNode, *LinkList;2、從鍵盤上依次輸入21、18、30、75、42、56，逆序創(chuàng)建單鏈表，并輸出單鏈表中的各元素值。

3、分別在單鏈表的第3個位置和第9個位置插入67和10，給出插入成功或失敗的信息，并輸出單鏈表中的各元素值4、刪除單鏈表中的第6個數(shù)據(jù)元素和第8個數(shù)據(jù)元素，給出刪除成功或失敗的信息，并輸出單鏈表中的各元素值四、完成情況和實驗記錄1、由于程序要求的操作很多，而且C程序要求敏感，所以在編程過程中只有通過不斷的修改，不斷的嘗試來克服遇到的很多錯誤和警告問題在調(diào)試過程要有足夠的耐心和發(fā)現(xiàn)錯誤的洞察力五、完成情況和實驗記錄#include#include#include #include #define LEN sizeof(LNode) //定義LEN為一個節(jié)點的長度enum BOOL{False,True}; //定義BOOL型typedef struct node{int data; //數(shù)據(jù)域 struct node *next;//指向下一個節(jié)點的指針}LNode,*LinkList;void CreatList(LinkList &,int); //生成一個單鏈表BOOL ListInsert(LinkList &,int,int); //在單鏈表中插入一個元素BOOL ListDelete(LinkList &,int,int); //在單鏈表中刪除一個元素void ListPrint(LinkList); //顯示單鏈表所有元素void main(){LinkList L; BOOL temp; int num,loc,flag=1,ch; char j; //程序說明 printf("單鏈表的基本操作。

\n"); printf("可以進行逆置，插入，刪除等操作\n"); printf("請輸入初始時鏈表長度:"); //輸入生成單鏈表時的元素個數(shù) scanf("%d",&num); CreatList(L,num); //生成單鏈表 ListPrint(L); while(flag) { printf("請選擇:\n"); printf("1.顯示所有元素\n"); //顯示鏈表元素 printf("2.插入一個元素\n"); //插入鏈表元素 printf("3.刪除一個元素\n"); //刪除鏈表元素 printf("0.退出程序 \n"); //退出 scanf(" %c",&j); switch(j) {case '1':ListPrint(L); break; case '2':{printf("請輸入數(shù)據(jù)和要插入的位置-1:\n");printf("格式：數(shù)據(jù)，位置；例如:12,3，（即把12插入到第3個位置之后，即第4個位置）\n"); scanf(" %d,%d",&ch,&loc); //輸入要插入的元素和要插入的位置 temp=ListInsert(L,loc,ch); //插入 if(temp==False) printf("插入失敗!\n"); //插入失敗 else printf("插入成功!\n"); //成功插入 ListPrint(L); break; }case '3':printf("請輸入要刪除的元素所在位置-1：（輸入2，即刪除的是第3個元素）:"); scanf("%d",&loc); //輸入要刪除的節(jié)點的位置 temp=ListDelete(L,loc,ch); //刪除 if(temp==False) printf("刪除失敗!\n"); //刪除失敗 else printf("成功刪除了一個元素:%d\n",ch); //刪除成功，顯示該元素 ListPrint(L); break; default:flag=0;printf("程序結(jié)束，按任意鍵退出!\n"); } }getchar();}void CreatList(LinkList &v,int n){//生成一個帶頭結(jié)點的有n個元素的單鏈表 int i; LinkList p; v=(LinkList)malloc(LEN); //生成頭結(jié)點 v->next=NULL; printf("請輸入%d個數(shù)據(jù)：例如：1 2 3\n",n); getchar(); for(i=n;i>0;--i) {p=(LinkList)malloc(LEN); //生成新結(jié)點 scanf("%d",&p->data); p->next=v->next; v->next=p; }}BOOL ListInsert(LinkList &v,int i,int e){//在單鏈表的第i各位置插入元素e，成功返回True，失敗返回False LinkList p,s; int j=0; p=v; while(p&&jnext;++j;} //查找第i-1個元素的位置 if(!p||j>i) return False; //沒有找到 s=(LinkList)malloc(LEN); //生成一個新結(jié)點 s->data=e; s->next=p->next; //將新結(jié)點插入到單鏈表中 p->next=s; return True;}BOOL ListDelete(LinkList &v,int i,int e){//在單鏈表中刪除第i個元素，成功刪除返回True，并用e返回該元素值，失敗返回False LinkList p,q; int j=0; p=v; while(p->next&&jnext;++j;} if(!(p->next)||j>i) return False; //查找失敗 q=p->next;p->next=q->next; //刪除該元素 e=q->data; //e取得該元素值 free(q); //釋放該元素空間 return True;}void ListPrint(LinkList v) {//顯示鏈表所有元素 LinkList q; q=v->next; printf("逆置輸出鏈表所有元素:"); while(q!=NULL) {printf("%d ",q->data);q=q->next;} printf("\n");}六、所輸入的數(shù)據(jù)及相應(yīng)的運行結(jié)果實驗二 棧、隊列算法設(shè)計一、實驗?zāi)康?、 熟悉棧這種特殊線性結(jié)構(gòu)的特性；2、 熟練掌握棧在順序存儲結(jié)構(gòu)和鏈表存儲結(jié)構(gòu)下的基本運算；3、 熟悉隊列這種特殊線性結(jié)構(gòu)的特性；4、 熟練掌握隊列在鏈表存儲結(jié)構(gòu)下的基本運算。

二、實驗內(nèi)容1、動態(tài)創(chuàng)建棧和隊列2、實現(xiàn)實現(xiàn)棧和隊列中元素的插入3、實現(xiàn)實現(xiàn)棧和隊列中元素的的刪除三、具體要求1、用順序和鏈?zhǔn)酱鎯Y(jié)構(gòu)分別實現(xiàn)棧的初始化、求長度、獲取棧頂元素、壓棧、出棧、判空、置空等操作，生成sqStack.h文件和LinkStack.h文件；編寫main函數(shù)調(diào)用四、程序清單順序棧#include#include#includeconst int stackIncreament=20;const int maxSize=50;template class Stack{public: Stack(int sz=50); ~Stack() {delete[]elements;} void Push(const T& x); int Pop(); int getTop(); bool IsEmpty() const {return (top==-1)?true:false;} bool IsFull() const {return (top==maxSize-1)?true:false;} int getSize() const {return top+1;} void MakeEmpty() {top=-1;} void print(Stack& s); void Meun();private: T *elements; int top; int maxSize; void overflowProcess();};template Stack::Stack(int sz):top(-1),maxSize(sz){ elements=new T[maxSize]; assert(elements!=NULL);};template void Stack::overflowProcess(){ T *newArray = new T[maxSize + stackIncreament]; if (newArray=NULL) { cerr<<"存儲分配失敗!"<