實 實 驗 報 告 （ （2018
/ 2019 學年 第 第 一 學期）
課程名稱 數(shù)據(jù)結構 實驗名稱 線性表及多項式的運算 實驗時間
2018 年
10 月
9 日
指導單位 現(xiàn)代郵政學院 指導教師 寧卓
學生姓名 唐棠 班級學號 B17100 學院(系) 現(xiàn)代郵政學院 專
業(yè)
物流管理
實 實 驗 報 告 實驗名稱 線性表及多項式的運算 指導教師 寧卓 實驗類型 設計 實驗學時 2 實驗時間 2 一、
實驗目的和要求 1、掌握線性表的兩種基本存儲結構及其應用場合：順序存儲和鏈接存儲。
2、掌握順序表和鏈表的各種基本操作算法。
3、理解線性表應用于多項式的實現(xiàn)算法。
二、 實驗環(huán)境( 實驗設備) 硬件：微型計算機 軟件：Windows 操作系統(tǒng)、Microsoft Visual C++6.0
2 三、實驗原理及內容 1、參照程序 2.1～2.7，編寫程序，完成順序表的初始化、查找、插入、刪除、輸出、撤銷等操作。
2、已知帶表頭結點單鏈表的類型定義如下：
typedef struct node { ElemType
element;
//結點的數(shù)據(jù)域 struct node *link;
//結點的指針域 }node; typedef struct
{ struct node * head; int n; }headerList; 參照程序 2.8～2.14，編寫程序，完成帶表頭結點單鏈表的初始化、查找、插入、刪除、輸出、撤銷等操作。
3、以題 2 所示帶表頭結點單鏈表為存儲結構，編寫程序實現(xiàn)單鏈表的逆置操作。（原單鏈表為（a 0 ，a 1 ，……，a n-1 ），逆置后為（a n-1 ，a n-2 ， ……，a 0 ），要求不引入新的存儲空間）
。
4、以題 2 所示帶表頭結點單鏈表為存儲結構，編寫程序實現(xiàn)將單鏈表排序成為有序單鏈表的操作。
5、已知帶表頭結點一元多項式的類型定義如下：
typedef struct pNode { int coef; int exp; struct pNode* link; } pNode; typedef struct
{
struct pNode *head; } polynominal; 編寫程序實現(xiàn)一元多項式的創(chuàng)建、輸出、撤銷以及兩個一元多項式相加和相乘的操作。
3
實 實 驗 報 告
4 2.1 #include<stdio.h> #include<stdlib.h> #define ERROR 0 #define OK 1 typedef int ElemType; typedef int Status;
typedef struct {
int n;
int maxLength;
ElemType *element;
}SeqList; Status Init(SeqList *L, int mSize) {
L->maxLength = mSize;
L->n = 0;
L->element = (ElemType*)malloc(sizeof(ElemType)*mSize);
if(!L->element)
return OK; } Status Find(SeqList L,int i,ElemType *x){
if(i<0||i>L.n-1){
return ERROR;
} *x=L.element[i];
return OK; } Status Insert(SeqList *L, int i, ElemType x) {
int j;
if (i<-1 || i>L->n - 1)
return ERROR;
if (L->n == L->maxLength)
return ERROR;
for (j = L->n - 1; j > i; j--) {
L->element[j + 1] = L->element[j];
5
}
L->element[i + 1] = x;
L -> n = L->n + 1;
return OK; } Status Delete(SeqList *L, int i){
int j; if(i<0||i>L->n-1){
return ERROR;
} if(!L->n){
return ERROR;
}
for(j=i+1;j<L->n;j++){
L->element[j-1]=L->element[j];
} L->n--;
return OK; } int Output(SeqList L) {
int i;
if (!L.n)
return ERROR;
for (i = 0; i <= L.n - 1; i++)
printf("%d ", L.element[i]);
return OK; } void Destroy(SeqList *L){
(*L).n=0;
(*L).maxLength=0;
free((*L).element); } void main() {
int i,x;
6
SeqList list;
Init(&list, 10);
for (i = 0; i < 9; i++) {
Insert(&list, i - 1, i);
}
Output(list);
printf("\n"); Delete(&list,0);
Output(list);
Find(list,2,&x);
printf("\nthe value is:");
printf("%d",x);
Destroy(&list); }
2.2 #include<stdio.h> #include<stdlib.h> typedef int ElemType; typedef int Status; #define ERROR 0 #define OK 1 typedef struct Node {
ElemType element;
struct Node * link;
}Node; typedef struct {
struct Node* head;
int n; }HeaderList; Status Init(HeaderList *h) {
h->head=(Node*)malloc(sizeof(Node));
if(!h->head){
return ERROR;
7
}
h->head->link = NULL;
h->n = 0;
return OK; } Status Find(HeaderList *h,int i,ElemType *x){
Node *p;
int j;
if(i<0||i>h->n-1){
return ERROR;
}
p=h->head->link;
for(j=0;j<i;j++){
p=p->link;
}
*x=p->element;
return OK; } Status Insert(HeaderList *h, int i, ElemType x) {
Node *p, *q;
int j;
if (i<-1 || i>h->n - 1)
return ERROR;
p = h->head;
for (j = 0; j <= i; j++) {
p = p->link;
}
q = (Node*)malloc(sizeof(Node));
q->element = x;
q->link = p->link;
p->link = q;
h->n++;
return OK; } Status Delete(HeaderList *h,int i){
8
int j;
Node *p,*q;
if(!h->n){
return ERROR;
if(i<0||i>h->n-1){
return ERROR;
}
}
q=h->head;
for(j=0;j<i;j++){
q=q->link;
}
p=q->link;
q->link=p->link;
free(p);
h->n--;
return OK; } Status Output(HeaderList *h) {
Node *p;
if (!h->n)
return ERROR;
p = h->head->link;
while (p) {
printf("%d ",p->element);
p = p->link;
}
return OK; } void Destroy(HeaderList *h){
Node *p,*q;
while(h->head->link){
q=h->head->link;
p=h->head->link->link;
free(h->head->link);
9
h->head=q;
} } void main() {
int i, x;
HeaderList list;
Init(&list);
for (i = 0; i < 9; i++) {
Insert(&list, i - 1, i);
}
printf("the linklist is:");
Output(&list);
Delete(&list,0);
printf("\nthe linklist is:");
Output(&list);
Find(&list,0,&x);
printf("\nthe value is:");
printf("%d ",x);
Destroy(&list); }
2.3 #include<stdio.h> #include<stdlib.h> typedef int ElemType; typedef int Status; #define ERROR 0 #define OK 1 typedef struct Node {
ElemType element;
struct Node * link;
}Node; typedef struct {
10
struct Node* head;
int n; }HeaderList; Status Init(HeaderList *h) {
h->head=(Node*)malloc(sizeof(Node));
if(!h->head){
return ERROR;
}
h->head->link = NULL;
h->n = 0;
return OK; } Status Find(HeaderList *h,int i,ElemType *x){
Node *p;
int j;
if(i<0||i>h->n-1){
return ERROR;
}
p=h->head->link;
for(j=0;j<i;j++){
p=p->link;
}
*x=p->element;
return OK; } Status Insert(HeaderList *h, int i, ElemType x) {
Node *p, *q;
int j;
if (i<-1 || i>h->n - 1)
return ERROR;
p = h->head;
for (j = 0; j <= i; j++) {
p = p->link;
}
q = (Node*)malloc(sizeof(Node));
11
q->element = x;
q->link = p->link;
p->link = q;
h->n++;
return OK; } Status Delete(HeaderList *h,int i){
int j;
Node *p,*q;
if(!h->n){
return ERROR;
if(i<0||i>h->n-1){
return ERROR;
}
}
q=h->head;
for(j=0;j<i;j++){
q=q->link;
}
p=q->link;
q->link=p->link;
free(p);
h->n--;
return OK; } Status Output(HeaderList *h) {
Node *p;
if (!h->n)
return ERROR;
p = h->head->link;
while (p) {
printf("%d ",p->element);
p = p->link;
}
return OK;
12 } void Destroy(HeaderList *h){
Node *p,*q;
while(h->head->link){
q=h->head->link;
p=h->head->link->link;
free(h->head->link);
h->head=q;
} } void Inverse(HeaderList *h){
Node *p=h->head->link,*q;
h->head->link = NULL;
while(p){
q=p->link;
p->link=h->head->link;
h->head->link=p;
p=q;
} } void main(){
int i, x;
HeaderList list;
Init(&list);
for (i = 0; i < 9; i++) {
Insert(&list, i - 1, i);
}
printf("the linklist is:");
Output(&list);
Inverse(&list);
printf("\nthe linklist is:");
Output(&list);
Destroy(&list); }
13
2.4 #include<stdio.h> #include<stdlib.h> typedef int ElemType; typedef int Status; #define ERROR 0 #define OK 1
typedef struct Node {
ElemType element;
struct Node * link;
}Node;
typedef struct {
struct Node* head;
int n; }HeaderList; Status Init(HeaderList *h) {
h->head=(Node*)malloc(sizeof(Node));
if(!h->head){
return ERROR;
}
h->head->link = NULL;
h->n = 0;
return OK; } Status Find(HeaderList *h,int i,ElemType *x){
Node *p;
int j;
if(i<0||i>h->n-1){
return ERROR;
}
p=h->head->link;
for(j=0;j<i;j++){
14
p=p->link;
}
*x=p->element;
return OK; } Status Insert(HeaderList *h, int i, ElemType x) {
Node *p, *q;
int j;
if (i<-1 || i>h->n - 1)
return ERROR;
p = h->head;
for (j = 0; j <= i; j++) {
p = p->link;
}
q = (Node*)malloc(sizeof(Node));
q->element = x;
q->link = p->link;
p->link = q;
h->n++;
return OK; } Status Delete(HeaderList *h,int i){
int j;
Node *p,*q;
if(!h->n){
return ERROR;
if(i<0||i>h->n-1){
return ERROR;
}
}
q=h->head;
for(j=0;j<i;j++){
q=q->link;
}
p=q->link;
15
q->link=p->link;
free(p);
h->n--;
return OK; } Status Output(HeaderList *h) {
Node *p;
if (!h->n)
return ERROR;
p = h->head->link;
while (p) {
printf("%d ",p->element);
p = p->link;
}
return OK; } void Destroy(HeaderList *h){
Node *p,*q;
while(h->head->link){
q=h->head->link;
p=h->head->link->link;
free(h->head->link);
h->head=q;
} } Status Order(HeaderList *h){
Node *s1,*s2,*s3,*s4,*p,*q;
for (p=h->head;p!=NULL && p->link!=NULL;p=p->link) {
for (q=p->link;q!=NULL && q->link!=NULL;q=q->link) {
if (p->link->element > q->link->element) {
s1=p->link;
s2=p->link->link;
s3=q->link;
s4=q->link->link;
if (s2!=s3) {
16
p->link=s3;
s3->link=s2;
q->link=s1;
s1->link=s4;
}
else {
p->link=s3;
s3->link=s1;
q=s3;
s1->link=s4;
}
}
}
}
return OK; } void main() {
int i,j, x;
HeaderList list;
Init(&list);
for (i = 8,j = 0; i >= 0; i--,j ++) {
Insert(&list, j - 1, i);
}
printf("the linklist is:");
Output(&list);
Order(&list);
printf("\nthe linklist is:");
Output(&list);
Destroy(&list); }
2.5 #include<stdio.h>
17 #include<stdlib.h>
typedef struct PNode{
int coef;
int exp;
struct PNode* link; }PNode;
typedef struct{
struct PNode *head; }polynominal; void Create(polynominal *p){
PNode *pn,*pre,*q;
p->head = (PNode*)malloc(sizeof(PNode));
p->head->exp = -1;
p->head->link = p->head;
for(;;){
pn=(PNode*)malloc(sizeof(PNode));
printf("coef:\n");
scanf("%d",&pn->coef);
printf("exp:\n");
scanf("%d",&pn->exp);
if(pn->exp<0) break;
pre = p->head;
q = p->head->link;
while(q && q->exp > pn->exp){
pre = q;
q = q->link;
}
pn->link = q;
pre->link = pn;
} } void Output(polynominal p){
PNode *q;
18
int flag = 1;
q = p.head->link;
if (!q){
return;
}
while(q != p.head){
if (!flag && (q->coef > 0)) printf("+");
flag = 0;
if(q->coef == 0){
return;
}
printf("%d",q->coef);
switch(q->exp){
case 0:break;
case 1:printf("X");break;
default:printf("X^%d",q->exp);break;
}
q = q->link;
} } void Add(polynominal *px,polynominal *qx){
PNode *q,*q1 = qx->head,*p, *p1,*temp;
p = px->head->link;
p1 = px->head;
q = q1->link;
while(p->exp >= 0){
while(p->exp < q->exp){
q1 = q;
q = q->link;
}
if(p->exp == q->exp){
q->coef = q->coef + p->coef;
if(q->coef == 0){
q1->link = q->link;
free(q);
19
q = q1->link;
p = p->link;
}
else{
q1 = q;
q = q->link;
p = p->link;
}
}
else{
temp = malloc(sizeof(PNode));
temp->coef = p->coef;
temp->exp = p->exp;
temp->link = q1->link;
q1->link = temp;
q1 = q1->link;
p = p->link;
}
} } void Multiply(polynominal *px,polynominal *qx){
polynominal qx1,qx2;
PNode *q1,*q2,*q3,*q4,*pre,*q;
qx1.head = (PNode*)malloc(sizeof(PNode));
qx1.head->exp = -1;
qx1.head->link = qx1.head;
q1 = px->head->link;
q2 = qx->head->link;
while(q2->exp != -1){
q3 = (PNode*)malloc(sizeof(PNode));
q3->coef = q1->coef * q2->coef;
q3->exp = q1->exp + q2->exp;
if(qx1.head->link->exp == -1){
q3->link = qx1.head->link;
qx1.head->link = q3;
20
pre = qx1.head->link;
}
else{
q3->link = qx1.head;
pre->link = q3;
pre = pre->link;
}
q2 = q2->link;
}
q1 = q1->link;
while(q1->exp != -1){
q2 = q2->link;
qx2.head = (PNode*)malloc(sizeof(PNode));
qx2.head->exp = -1;
qx2.head->link = qx2.head;
while(q2->exp != -1){
q4 = (PNode*)malloc(sizeof(PNode));
q4->coef = q1->coef * q2->coef;
q4->exp = q1->exp + q2->exp;
if(qx2.head->link->exp == -1){
q4->link = qx2.head->link;
qx2.head->link = q4;
pre = qx2.head->link;
}
else{
q4->link = qx2.head;
pre->link = q4;
pre = pre->link;
}
q2 = q2->link;
}
Add(&qx2,&qx1);
q1 = q1->link;
}
Output(qx1);
21 }
int main(){
polynominal p,q;
int x;
printf("Please enter the first poly:\n");
Create(&p);
Output(p);
printf("\n\nPlease enter the second poly:\n");
Create(&q);
Output(q);
printf("\n\nPlease choose the function:\n");
scanf("%d",&x);
switch(x){
case 0:printf("Add:\n");
Add(&p,&q);
Output(q);
break;
case 1:printf("Multiply:\n");
Multiply(&p,&q);
default:break;
}
return 0; }
實 實 驗 報 告
22 實 實 驗 報 告 實 實 驗 報 告 四、實驗小結 （包括問題和解決方法、心得體會、意見與建議等）
(一)實驗中遇到的主要問題及解決方法
在題目一編譯時，總出現(xiàn)問題，發(fā)現(xiàn)是沒有初始化線性表所導致的錯誤，進行重新定義線性表的修改后錯誤消除； 在題目二到五編譯運行時，出現(xiàn)了沒有檢查下標越界問題，后來用百度方法查找，進行增加判斷下標是否越界的修改后錯誤消除，從而說明在程序運行過程中需要防止下標越界，避免出現(xiàn)覆蓋內存導致運行出現(xiàn)錯誤； 在題目運行時，出現(xiàn)了代碼的變量命名，標點符號缺失問題，后來根據(jù)下方的提示欄出現(xiàn)的錯誤和提醒方法查找，修改后錯誤消除，從而說明寫代碼很容易出錯；
（二）實驗心得
本學期第一次數(shù)據(jù)結構實驗設計結束了，感覺學到了很多知識。這次 C 語言數(shù)據(jù)結構程序設計剛拿到要完成的題目時，感覺程序要求的一個個實現(xiàn)功能完成起來不是很難，但是當真的開始思考怎么去寫代碼，怎么去安排程序結構，怎么去實現(xiàn)想要的程序功能等等一系列的事情就發(fā)現(xiàn)問題很大，任務很重；特別是在調試程序的時候更是讓人頭痛，辛辛苦苦的寫好了函數(shù)，等到調試運行就出現(xiàn)一堆錯誤通過這次編程我們深深的感受到對代碼的變量命名，代碼內注釋格式，甚至嵌套中行縮進的長度和函數(shù)間的空行數(shù)字都有明確規(guī)定，良好的編寫習慣，不但有助于代碼的移植和糾錯，也有助于不同人員之間的協(xié)作。這個程序設計主要涉及到了線性表在多項式和其他方面的應用。只有充分掌握了線性表的定義初始化等這些內容，才有可能組織好這些代碼，使之符合運算邏輯，得到理想的結果。
善于總結，也是學習能力的一種體現(xiàn)，每次完成一個編程任務，完成一段代碼，都應當有目的的跟蹤該程序的應用狀況，隨時總結，找到自己的不足，這樣所編寫的程序才能逐步提高，生活就是這樣，汗水預示著結果也見證著收獲。的確，自從拿到題目到完成整個編程，從理論到實踐，在一次實驗過程內，可以學到很多很多的東西，同時不僅可以鞏固了以前所學過的知識，而且學到了很多在書本上所沒有學到過的知識。通過完成這種實驗實踐使我懂得了理論與實際相結合是很重要的，只有理論知識是遠遠不夠的，只有把所學的理論知識與實踐相結合起來，從理論中得出結論，才能提高自己的實際動手能力和獨立思考的能力。
23
（三）意見與建議（沒有可省略）
實驗設計上機實踐對個人的編程能力有很高的要求，每個人的能力水平不太一樣，有的時候可以講一些基礎的知識先過渡，比如怎么初始化變量，算法的基本思路等等，然后再由淺入深。
24
五、 支撐畢業(yè)要求指標點 《數(shù)據(jù)結構》課程支撐畢業(yè)要求的指標點為：
1.2-M 掌握計算機軟硬件相關工程基礎知識，能將其用于分析計算機及應用領域的相關工程問題。
3.2-H 能夠根據(jù)用戶需求，選取適當?shù)难芯糠椒ê图夹g手段，確定復雜工程問題的解決方案。
4.2-H 能夠根據(jù)實驗方案，配置實驗環(huán)境、開展實驗，使用定性或定量分析方法進行數(shù)據(jù)分析與處理，綜合實驗結果以獲得合理有效的結論。
實驗內容 支撐點 1.2 支撐點 3.2 支撐點 4.2 線性表及多項式的運算 √
二叉樹的基本操作及哈夫曼編碼譯碼系統(tǒng)的實現(xiàn)
√ √ 圖的基本運算及智能交通中的最佳路徑選擇問題
√ √ 各種內排序算法的實現(xiàn)及性能比較 √
√
六、指導教師評語 ( 含學生能力達成度的評價)
如評分細則所示
成 成
績 XX 批閱人 XX 日 日
期 XXX
評
分
細
則 評分項 優(yōu)秀 良好 中等 合格 不合格 遵守實驗室規(guī)章制度
學習態(tài)度
算法思想準備情況
程序設計能力
解決問題能力
課題功能實現(xiàn)情況
算法設計合理性
算法效能評價
回答問題準確度
報告書寫認真程度
內容詳實程度
文字表達熟練程度
其它評價意見
本次實驗能力達成評價（總成績）
25
推薦訪問： 數(shù)據(jù)結構 課內 實驗上一篇：保密工作自查報告(精選)
下一篇：土地自查報告(精選)
在偉大祖國73華誕之際，我參加了單位組織的“光影鑄魂”主題黨日活動，集中觀看了抗美援朝題材影片《長津湖》，再一次重溫這段悲壯歷史，再一次深刻感悟偉大抗美援朝精神。1950年10月，新中國剛剛成立一年，
根據(jù)省局黨組《關于舉辦習近平談治國理政（第四卷）讀書班的通知》要求，我中心通過專題學習、專題研討以及交流分享等形式，系統(tǒng)的對《習近平談治國理政》（第四卷)進行了深入的學習與交流，下面我就來談一談我個人
《習近平談治國理政》（第四卷）是在百年變局和世紀疫情相互疊加的大背景下，對以習近平同志為核心的黨中央治國理政重大戰(zhàn)略部署、重大理論創(chuàng)造、重大思想引領的系統(tǒng)呈現(xiàn)。它生動記錄了新一代黨中央領導集體統(tǒng)籌兩個
《真抓實干做好新發(fā)展階段“三農工作”》是《習近平談治國理政》第四卷中的文章，這是習近平總書記在2020年12月28日中央農村工作會議上的集體學習時的講話。文章指出，我常講，領導干部要胸懷黨和國家工作大
在《習近平談治國理政》第四卷中，習近平總書記強調，江山就是人民，人民就是江山，打江山、守江山，守的是人民的心。從嘉興南湖中駛出的小小紅船，到世界上最大的執(zhí)政黨，在中國共產(chǎn)黨的字典里，“人民”一詞從來都
黨的十八大以來，習近平總書記以馬克思主義戰(zhàn)略家的博大胸襟和深謀遠慮，在治國理政和推動全球治理中牢固樹立戰(zhàn)略意識，在不同場合多次圍繞戰(zhàn)略策略的重要性，戰(zhàn)略和策略的關系，提高戰(zhàn)略思維、堅定戰(zhàn)略自信、強化戰(zhàn)
《習近平談治國理政》第四卷集中展示了以習近平同志為核心的黨中央在百年變局和世紀疫情相互疊加背景下，如何更好地堅持和發(fā)展中國特色社會主義而進行的生動實踐與理論探索；對于新時代堅持和發(fā)展什么樣的中國特色社
在黨組織的關懷下，我有幸參加了區(qū)委組織部組織的入黨積極分子培訓班。為期一周的學習，學習形式多樣，課程內容豐富，各位專家的講解細致精彩，對于我加深對黨的創(chuàng)新理論的認識、對黨的歷史的深入了解、對中共黨員的
《習近平談治國理政》第四卷《共建網(wǎng)上美好精神家園》一文中指出：網(wǎng)絡玩命是新形勢下社會文明的重要內容，是建設網(wǎng)絡強國的重要領域。截至2021年12月，我國網(wǎng)民規(guī)模達10 32億，較2020年12月增長4
剛剛召開的中國共產(chǎn)黨第十九屆中央委員會第七次全體會議上討論并通過了黨的十九屆中央委員會向中國共產(chǎn)黨第二十次全國代表大會的報告、黨的十九屆中央紀律檢查委員會向中國共產(chǎn)黨第二十次全國代表大會的工作報告和《