实验二线性表

1、实验目的

（1）熟悉将算法转换为程序代码的过程。

（2）了解顺序表的逻辑结构特性，熟练掌握顺序表存储结构的C语言描述方法。

（3）熟练掌握顺序表的基本运算：查找、插入、删除等，掌握顺序表的随机存取特性。

（4）了解线性表的链式存储结构，熟练掌握线性表的链式存储结构的C语言描述方法。

（5）熟练掌握线性链表（单链表）的基本运算：查找、插入、删除等，能在实际应用中灵活选择适当的链表结构。

2、实验内容

（1）操作顺序表

用实验一的原始数据构造一顺序表，命名为 gradeList
向 gradeList 中插入如下记录：

张兰， 85， 77， 92 //插入为第7条记录

王平， 92， 83, 79 // 插入为第 2条

冯文成，77，68， 80 / 插入为最后一条
搜寻 gradeList，找到第2，12，和最后一条记录
搜寻 gradeList，找到 “令狐冲”，’陈海生”的所有成绩。
删除 gradeList 中 “岳不群”的成绩记录。

（2）操作链表

建立两个整数单链表,命名为LA 和 LB, 分别含有如下整数：

LA: 78, 64, 37, 30, 29, 24, 18, 12, 9, 2

LB: 93, 82, 73, 65, 44, 35, 31, 28, 26, 17, 15

编制一程序将LA与LB合并成新的链表LC， LC的数据仍然要保持降序；然后将LC的数据输出到屏幕上,并在其后显示LC的长度。然后完成如下操作：

找到LC中元素65的位置并显示在屏幕上
删除LC中的如下值：82,73,64,29
显示上一步操作完成后LC的数据。
再向LC中插入数55，43，同时保持LC 中数据按降序排列；然后屏幕显示LC中所有数据。

3、实验要求：
（1）实验报告中需要显示所建立的抽象数据模型。
（2）每个功能需要编制一专门的函数实现其功能：例如：建立函数 CreateLA（）实现建立单向链表LA；建立函数 MergeLists（）实现合并LA与LB 等的。
（3）将程序运行结果截图写入实验报告。
（4）实验需要在两周内按时完成。

学习资料:

相关代码

顺序表:

#include<fstream>  
#include<stdlib.h>  
#include <iostream> 
#include <iomanip>
using namespace std;  
/*构造结构体结点*/  
typedef struct data{  
    int num;  
    data*next;  
}Data;  
Data \*CreatL(int\*a,int size);  
void view_list(Data*L);  
void view_length(Data*L);  
int output_length(Data*L);  
void view_location(Data *L,int a);  
void delete_num(Data*L,int a);  
void Insert(Data*L,int a);  
Data * MergeLists(Data\*LA,Data\*LB);  
int main(){  
    int a\[\]={78, 64, 37, 30, 29, 24, 18, 12, 9, 2};  
    int b\[\]={93, 82, 73, 65, 44, 35, 31, 28, 26, 17, 15};  
    Data*LA=CreatL(a,10);  
    Data*LB=CreatL(b,11);     
    Data*LC=MergeLists(LA,LB);  
    cout<<"LC: ";
    view_list(LC);
    cout<<endl;
    view_length(LC);
    cout<<endl;
    //（1）找到LC中元素65的位置并显示在屏幕上  
    view_location(LC,65);  
    //（2）删除LC中的如下值：82,73,64,29;  
    delete_num(LC,82);  
    delete_num(LC,73);  
    delete_num(LC,64);  
    delete_num(LC,29);  
    //（3）显示上一步操作完成后LC的数据。  
    cout<<"删除LC中的如下值：82,73,64,29"<<endl;
    cout<<"LC: ";
    view_list(LC); 
	cout<<endl<<endl; 
    //（4）再向LC中插入数55，43；然后屏幕显示LC中所有数据。  
    Insert(LC,55);  
    Insert(LC,43);  
    cout<<"向LC中插入数55，43"<<endl;
    cout<<"LC: ";
    view_list(LC);  
    return 0;  
}  
Data \*CreatL(int\*a,int size){
    /*初始化单链表表a*/
    Data\*head=(Data\*)malloc(sizeof(Data));  //分配空间 
    head->num=0;  
    head->next=NULL;  
    Data \*p=head,\*q;  
    q=p;  
    for(int i=0;i<size;i++){  
        p=(Data*)malloc(sizeof(Data));  
        p->num=a\[i\];  
        q->next=p;  
        q=p;  
    }p->next=NULL;  
    return head;  
}  
  
void view_list(Data*L){
	/*查看链表数据*/  
    Data*p=L;  
    while(p->next){  
        p=p->next;  
        cout<<p->num<<setw(3);    
    }  
}  
void view_length(Data*L){
	/*输出链表长度*/ 
    Data*p=L;  
    int i=0;  
    while(p->next){  
        p=p->next;  
        i++;      
    }  
    cout<<"The length of the list is "<<i<<endl;  
}  
int output_length(Data*L){  
	/*返回链表长度*/ 
    Data*p=L;  
    int i=0;  
    while(p->next){  
        p=p->next;  
        i++;      
    }  
    return i;  
}  
void view_location(Data *L,int a){  
	/*输出a在单链表L的位置*/ 
    Data*p=L;  
    int i=0;  
    while((p->num!=a)&&(p->next!=NULL)){  
        p=p->next;  
        if(p->num==a)  
        cout<<"The location of num:"<<a<<" in the list is "<<i<<" !"<<endl;  
        i++;      
    }  
}  
void delete_num(Data*L,int a){
	/*删除L中第一个出现的a*/ 
    Data\*p=L,\*q=p;  
    int i=0;  
    while(p->next){  
        p=p->next;  
        if(p->num==a){  
            q->next=p->next;  
            free(p);  
            break;  
        }  
        q=p;  
    }  
    if(!p->next)cout<<"Cannot find num:"<<a<<" to delete!"<<endl;  
}  
void Insert(Data*L,int a){
	/*单链表按降序插入*/  
    Data\*p=L,\*q=p,*ptemp;  
    int i=0;  
    while(p->next){  
        p=p->next;  
        if((p->num)<=a){  
            ptemp=(Data*)malloc(sizeof(Data)); //给指针变量ptemp分配一个数据空间 
            ptemp->num=a;   //将节点*ptemp的数据域置为a 
            ptemp->next=p;  //将节点*ptemp的指针域指向
            q->next=ptemp;  //将节点\*q的指针域指向\*ptemp
            break;  
        }  
        q=p;  
        i++;  
    }  
    if(i==output_length(L)){  
        ptemp=(Data*)malloc(sizeof(Data));  
        ptemp->next=NULL;  
        ptemp->num=a;  
        p->next=ptemp;  
    }  
}  
Data * MergeLists(Data\*LA,Data\*LB){  
	/*单链表合并*/ 
    Data *LC=LB;  
    Data *p1=LA->next;  
    Data *p2=p1;  
    while(p2->next){  
        p2=p1;  
        Insert(LB,p1->num);  //将LA的数据域赋给LB 
        p1=p1->next;  
    }  
    return LC;  
}

链表:

#include<stdlib.h>  
#include<string.h>  
#define Addsize 5  


#include <fstream>  
#include <string>   
#include <sstream>
#include<stdlib.h>  
#include<string.h>
using namespace std; 
typedef struct{  
    /*定义结点结构体*/   
    char name\[10\];  
    int analysis;  
    int algebra;  
    int anaGeo;  
}student;  
typedef struct{  
    /*定义顺序表结构体*/  
    //这个结构体包含一个顺序表所具有的三个基本信息;   
    student *elem;//顺序表的首地址;   
    int length;//顺序表的有效数据长度;  
    int listsize;//顺序表所占系统分配的内存空间;   
}gradeList;  
  
void Initlist(gradeList&L);  
void file\_to\_stu(FILE\*fp,student\*stu);  
void Add(gradeList&L,student stu);  
void show_all(gradeList &L);  
void search_stu(gradeList&L,char *info);  
void search_num(gradeList&L,int num);  
void delete_stu(gradeList&L,char *info);  
int  Insert(gradeList&L,student stu,int e);  
  
int main(){  
    gradeList L;//定义一个顺序表变量L;  
    Initlist(L);//初始化L;   
    student stu\[14\];//定义一个学生结构体数组stu;   
    char info\[10\];  
    FILE *fp;   
    file\_to\_stu(fp,stu);  
    for(int i=0;i<14;i++){  
        //将结构体数组stu中的14个学生信息加到顺序表L中;   
        Add(L,stu\[i\]);  
    }  
    //题目2:向 gradeList中插入如下记录:"张兰, 85,77,92"此记录插入7条记录上  
    student stu1={"王平",92,83,79};  
    Insert(L,stu1,2);
    student stu2={"张兰",85,77,92};  
    Insert(L,stu2,7);
	student stu3={"冯文成",77,68,80};  
    Insert(L,stu3,17); 
    //题目3:搜寻 gradeList，找到第12条记录  
	search_num(L,2);   
    search_num(L,12); 
	search_num(L,17);   
    //题目4:搜寻 gradeList，找到"令狐冲"的所有成绩。  
    strcpy(info,"令狐冲");  
    search_stu(L,info);  
    //题目5:删除 gradeList 中 "岳不群"的成绩记录   
    strcpy(info,"岳不群");  
    delete_stu(L,info);  
    show_all(L);  
    return 0;  
}  
void Initlist(gradeList&L){//init既是initialize(初始化)的缩写词;   
    /*初始化顺序表L*/  
    L.elem=(student*)malloc(20*sizeof(student));  
    if(!L.elem)exit(1);//判断是否初始化成功;   
    L.length=0;//因为初始化的顺序表无有效数据故为0;   
    L.listsize=20;//此时顺序表L所占系统分配内存为20(个student结构体);  
}  
void Add (gradeList&L,student stu){  
    /*这个函数实现将一个学生结构体加到顺序表的最尾端 
       是为了实现一开始将14个学生信息加到顺序表而用的*/   
    L.length++;//每次增加一个学生信息，顺序表L的有效数据长度就加一;  
    L.elem\[L.length-1\]=stu;//让顺序表L的最后一个位置加上要等于增加的学生结构体;  
}  
int Insert (gradeList&L,student stu,int e){  
    /*实现在顺序表的e位置插入学生结构体stu的功能，参考书里22页的代码*/   
    student *newbase;//用于指向新的分配内存的指针;  
    student \*p=NULL,\*q=NULL;  
      
    if(L.length+1<e||e<1){  
        /*防止用户输入的位置超出顺序表L的有效空间*/   
        printf("插入序号越出顺序表！！！");  
        return 0;  
    }  
    if(L.length>=L.listsize){  
        //当前分配的空间不够用，增加分配;   
        newbase=(student*)realloc(L.elem,(L.listsize+Addsize)*sizeof(student));  
        if(!newbase){  
        printf("分配新空间失败！");   
        exit(1);  
        }  
        L.elem=newbase;//让原来顺序表L的成员指针指向新分配的空间；   
        L.listsize+=Addsize; //顺序表L的占用分配空间要记得加上新增的空间;  
    }  
    q=&(L.elem\[e-1\]);//让指针q先指向所要插入的位置地址;   
    for(p=&(L.elem\[L.length-1\]);p>=q;--p){  
        //从最后一个结构体依次往后退到第e-1个位置为止;   
        *(p+1)=*p;  
    }  
    *q=stu;//让刚刚指向第e个为止的指针q的元素值等于stu   
    L.length++;//因为插入一个新的结构体，所以有效长度要加一；   
    return 1;  
}  
void show_all(gradeList &L){  
    /*将顺序表L的所有有效数据打印在屏幕上*/  
    for(int i=0;i<L.length;i++){  
        printf("%s\\t",L.elem\[i\].name);  
        printf("%d\\t",L.elem\[i\].analysis);  
        printf("%d\\t",L.elem\[i\].algebra);  
        printf("%d\\n",L.elem\[i\].anaGeo);  
    }  
}  
void search_stu(gradeList&L,char *info){  
    /*在顺序表L里查找姓名为info的结构体，并将信息打印在屏幕上*/  
    for(int i=0;i<L.length;i++){  
        if(!strcmp(L.elem\[i\].name,info))  
        {//如果在顺序表L找到和info同名的结构体则进入循环;  
         //将该学生结构体的信息打印在屏幕上;  
            printf("你所要搜索的信息如下:\\n");  
            printf("%s\\t",L.elem\[i\].name);  
            printf("%d\\t",L.elem\[i\].analysis);  
            printf("%d\\t",L.elem\[i\].algebra);  
            printf("%d\\n\\n",L.elem\[i\].anaGeo);break;  
        }  
    }  
}  
void search_num(gradeList&L,int num){  
    /*在顺序表L里查找第num个的结构体，并将信息打印在屏幕上*/  
    for(int i=0;i<L.length;i++){  
        if(i==num-1){  
            printf("你所要搜索的信息如下:\\n");  
            printf("%s\\t",L.elem\[i\].name);  
            printf("%d\\t",L.elem\[i\].analysis);  
            printf("%d\\t",L.elem\[i\].algebra);  
            printf("%d\\n\\n",L.elem\[i\].anaGeo);break;  
        }  
    }  
}  
void file\_to\_stu(FILE\*fp,student\*stu){  
    if((fp=fopen("Scores.txt","rt"))==NULL){  
    //检测文件打开是否正常并打开文件。  
        printf("open error!");  
        exit(1);  
    }  
    for(int i=0;i<14;i++){  
    //将文件“scores.txt”里面的14个学生信息弄到结构体数组stu中;   
    fscanf(fp,"%s%d%d%d",&stu\[i\].name,&stu\[i\].analysis,&stu\[i\].algebra,&stu\[i\].anaGeo);  
          
    }  
}  
void delete_stu(gradeList&L,char *info){  
    /*在顺序表L里查找姓名为info的结构体，并将该结构体删除*/  
    for(int i=0;i<L.length;i++){  
        if(!strcmp(L.elem\[i\].name,info)){  
            //如果在顺序表L找到和info同名的结构体则进入循环;  
            for(int j=i;j<L.length;j++){  
                L.elem\[j\]=L.elem\[j+1\];  
            }break;  
        }  
    }L.length--;//因为删除了一个数据，所以有效数据要减一;  
}

实验二 线性表

实验二线性表