第二章 线性表

1.线性表的定义和特点

• 存在唯一一个“第一个”元素
• 存在唯一一个“最后一个”元素
• 除第一个元素外，每一个元素都有且只有一个直接前驱
• 除最后一个元素外，每个元素都有且只有一个直接后继

2.线性表的顺序表示

3.线性表的链式表示

4.实验报告

（1） 编程实现顺序表的基本操作（建立、插入、删除、输出、顺序查找、折半查找、排序等），并设计一个菜单调用。

com_def.h

#include <stdio.h> 
#include <iostream>
#include <iomanip>
#include <string.h>
#include <malloc.h>
#include <process.h>
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define OVERFLOW -1
typedef int Status;

sqlist_def.h

#define LIST_INIT_SIZE 100//线性表存储空间的初始分配量
#define LISTINCREMENT 10//线性表存储空间的分配增量
typedef int ElemType;
typedef struct{
 ElemType *elem; //存储空间的首地址
 int length; //当前长度 
 int listsize; //当前分配的存储容量 
}Sqlist;

sqlist_func.h

#include "com_def.h"
using namespace std;
Status InitList_Sq(Sqlist &L);
Status ListInsert_Sq(Sqlist &L,int i,ElemType e);
Status Show(Sqlist L);
Status GetElem(Sqlist L, int i,ElemType &e);
Status LocateElem(Sqlist L, ElemType e);
Status BubbleSort(Sqlist L);
Status Binary_Search(Sqlist &L, int &i,ElemType e);

Status InitList_Sq(Sqlist &L){
 //构造一个空的线性表
 int n,i;
 L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));
 if(!L.elem) exit(OVERFLOW);  //存储分配失败
 cout<<endl<<"请输入元素个数：";
 cin>>n;
 cout<<"请输入这"<<n<<"个元素:"<<endl;
 for(i=0;i<n;i++){
  cin>>L.elem[i];
 }
 
 L.length=n;//空表长度为 0 
 L.listsize=LIST_INIT_SIZE;//初始存储容量
 return OK; 
}
Status ListInsert_Sq(Sqlist &L,int i,ElemType e){
 //在顺序线性表L中第i个位置之前插入新的元素e
 //i的合法值为1<=i<=ListLength_sq(L)+1
 ElemType *p;
 if(i<1||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) exit(OVERFLOW);//存储分配失败 
  L.elem=newbase;//新的首地址 
  L.listsize+=LISTINCREMENT;//增加存储容量 
 }
 ElemType *q=&(L.elem[i-1]);//q为插入位置的地址 
 for(p=&(L.elem[L.length-1]);p>=q;--p){
  *(p+1)=*p;//插入位置及之后的元素右移  
 } 
 *p=e;//插入e
 ++L.length;//表长增加1
 return OK;
  
}

Status ListDelete_Sq(Sqlist &L,int i,ElemType &e){
 //在顺序线性表L中删除第i个元素，并用e值返回
 //i的合法值为1<=i<=ListLength_Sq(L)
 ElemType *p,*q;
 if(i<1||i>L.length) return ERROR;//i的值不合法
 p=&(L.elem[i-1]);//p为删除元素的位置
 e=*p;//被删除的元素的值赋给e
 q=L.elem+L.length-1;//表尾元素的位置
 for(++p;p<=q;++p){
  //被删除元素之后的元素左移 
  *(p-1)=*p; 
 } 
 --L.length;//表长减一 
 return OK; 
  
}

Status Show(Sqlist L)
{
 int i;
 cout<<"此时表中现有的元素为：\n";
 for(i=0;i<L.length;i++)
 {
  cout<<L.elem[i]<<endl;
 }
}

Status GetElem(Sqlist L, int i,ElemType &e)
{
 
 if(i<1||i>L.length) return ERROR;
 e=L.elem[i-1];
 return OK; 
}

Status LocateElem(Sqlist L, ElemType e){
 int i;
 ElemType *p;
 i=1;
 p=L.elem;
 while(i<=L.length&&*p!=e){
  ++i;
  p++;
 }
 if(i<=L.length) return i;
 else return 0;
}

Status BubbleSort(Sqlist L){
 //冒泡排序 
 int i,j;
 ElemType temp;
 for(i=0;i<L.length;i++)
 {
  for(j=1;j<L.length-i;j++)
  {
   if(L.elem[j-1]>L.elem[j])
   {
    temp=L.elem[j];
    L.elem[j]=L.elem[j-1];
    L.elem[j-1]=temp;
   }
  }  
 }
}

Status Binary_Search(Sqlist &L, int &i,ElemType e){
 //折半查找法 
 BubbleSort(L);
    int low=0,high=L.length-1,mid;     //置当前查找区间上、下界的初值
    while(low<=high)
    {
        if(L.elem[low]==e)
            i= low;
        if(L.elem[high]==e)
            i= high;          
        mid=low+((high-low)/2);
            /*使用(low+high)/2会有整数溢出的问题
            （问题会出现在当low+high的结果大于表达式结果类型所能表示的最大值时，
              这样，产生溢出后再/2是不会产生正确结果的，而low+((high-low)/2)
              不存在这个问题*/
        if(L.elem[mid]==e)
          i= mid;             //查找成功返回
        if(L.elem[mid]<e)
          low=mid+1;              
        else
          high=mid-1;             
    }
    if(low>high)
        return ERROR;//当low>high时表示所查找区间内没有结果，查找失败
}

Status QucikSort(Sqlist &L){
 int i, j,key;      /*定义变量为基本整型*/
    i = start;         /*将每组首个元素赋给i*/
    j = end;     /*将每组末尾元素赋给j*/
    key = L.elem[start];   /*设置基准值*/
    while (i < j)
    {
        while (i < j && key< L.elem[j])
            j--;    /*位置左移*/
        if (i < j)
        {
            L.elem[i] = L.elem[j];  /*将s[j]放到s[i]的位置上*/
            i++;     /*位置右移*/
        }
        while (i < j && L.elem[i] <= L.elem[0])
            i++;    /*位置右移*/
        if (i < j)
        {
            L.elem[j] = L.elem[i];  /*将大于基准值的s[j]放到s[i]位置*/
            j--;    /*位置右移*/
        }
    }
    L.elem[i] = key;    /*将基准值放入指定位置*/
    if (start < i)
        QucikSort(L, start, j - 1);/*对分割出的部分递归调用函数qusort()*/
    if (i < end)
       QucikSort(L, j + 1, end); 
}

main.cpp

#include "com_def.h"
#include "sqlist_def.h"
#include "sqlist_func.h"
using namespace std;
//1,6,8
int main(){
 Sqlist L;
 InitList_Sq(L); 
 //cout<<L.length<<endl; 
 int i,n;
 ElemType e;
 int choice=0;
 do{
  cout<<"***********************"<<endl;
  cout<<"* 1.插入元素          *\n";
  cout<<"* 2.删除元素          *\n";
  cout<<"* 3.输出元素          *\n";
  cout<<"* 4.按位置查找元素    *\n";
  cout<<"* 5.按值查找元素      *\n";
  cout<<"* 6.折半查找元素      *\n";
  cout<<"* 7.线性表冒泡排序    *\n";
  cout<<"* 8.线性表快速排序    *\n";
  cout<<"* 0.退出              *\n";
  cout<<"***********************"<<endl;
  cout<<"请输入你的选择:";
  cin>>choice;  
  switch(choice)
  {
   case 1:
    {
     cout<<"请输入插入位置和插入的数值"<<endl;
     cin>>i>>e;
     if(ListInsert_Sq(L,i,e)==OK)
     {
        cout<<"插入成功!"<<endl<<endl;
        Show(L);
     }
     else{
      cout<<"插入失败!"<<endl<<endl;
      Show(L);
     }
     break; 
    }
   case 2:
    {
     cout<<"请输入删除位置"<<endl;
     cin>>i;
     if(ListDelete_Sq(L, i, e))
     {
     cout<<"删除成功"<<endl;
     }
     else
     {
     cout<<"删除失败"<<endl;
     }
     cout<<"删除位置的值为"<<e<<endl;
     break;
    }
   case 3:
    {
     Show(L);
     break;
    }
   case 4:
    {
     cout<<"请输入查找的位置:";
     cin>>i;
     if(GetElem(L, i, e))
     {
      cout<<"查找成功!"<<endl;
      cout<<"查找位置的值为:"<<e<<endl;
     }
     else
     {
      cout<<"查找失败!"<<endl;
     }
     
     break; 
     } 
    case 5:
     {
      cout<<"请输入查找的值:";
     cin>>e;
     if(LocateElem(L, e))
     {
      cout<<"查找成功!"<<endl;
     }
     else
     {
      cout<<"查找失败!"<<endl;
     }
     cout<<"查找值的位置为:"<<i+1<<endl;
     break;
     }
   case 6:
    {
     cout<<"升幂排序"<<endl;
     BubbleSort(L);
     Show(L);
        cout<<"请输入查找数值:";
     cin>>e;
     if(!Binary_Search(L, i, e))
     {
     cout<<"查找成功"<<endl;
     }
     else
     {
     cout<<"查找失败"<<endl;
     }
     cout<<"查找数值的位置为:"<<i+1<<endl;
     break;
    }
   case 7:
    {
     cout<<"冒泡排序："<<endl;
     BubbleSort(L);
     Show(L);
     break;
    }
   case 8:
    {
     cout<<"快速排序："<<endl;
     QucikSort(L);
     Show(L);
     break;
    }             
  }//switch后 
 }while(choice!=0) ;
}

（2） 编程实现单链表的基本操作（建立、插入、删除、求表长、顺序查找、逆置、有序表的合并等），并设计一个菜单调用。

com_def.h

#include <stdio.h> 
#include <iostream>
#include <iomanip>
#include <string.h>
#include <malloc.h>
#include <process.h>
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define OVERFLOW -1
typedef int Status;

linklist_def.h

typedef int ElemType;
typedef struct LNode{
 ElemType data;
 struct LNode *next;
}LNode,*LinkList;

linklist_func.h

#include "com_def.h"
using namespace std;
 /*初始化空表*/
Status Init_Linklist(LinkList &L)
{   
 int i,n;
 LinkList p,q;//p是指向第i个元素的指针 
    L=(LinkList)malloc(sizeof(LNode));
    if(!L) exit(OVERFLOW);
    L->next=NULL;// 空链表 
    q=L;//q为尾指针
 cout<<"利用尾插法开始建立链表！"<<endl; 
    cout<<endl<<"请输入元素的个数：";
 cin>>n;
 cout<<"输入 "<<n<<" 个元素:"<<endl; 
 for(i=1;i<=n;i++){
  p=(LinkList)malloc(sizeof(LNode));
  if(!p) exit(OVERFLOW);
  cin>>p->data;//元素的值存入链表 
  q->next=p;//下一个元素的地址赋给上一个元素的指针起到链接的作用 
  q=p;//再把p的地址赋给q 
 } 
 q->next=NULL;//创建链表完成 尾指针指空 
    return OK;
}
void OutputLinklist(LinkList &L){
 LinkList p;
 p=L->next;
 while(p){
  cout<<p->data;
  p=p->next;
 }
 cout<<endl; 
}
Status GetElem(LinkList &L,int i,ElemType &e){
 int j=1;
 LinkList p=L->next;
 while(p&&j<i)
 {
  p=p->next;
  j++;
 }
 if(!p||j>i) return ERROR;
 e=p->data;
 return OK;
}
Status Insert_Linklist(LinkList &L,int i,ElemType e){
 LinkList p,s;//s指向i-1个结点 
 int j=0;//j计数 
 p=L;//p为尾节点 
 while(p&&j<i-1)
 {
  p=p->next;
  ++j;//寻找第i-1个结点 
 }
 if(!p||j>i+1) return ERROR;
 s=(LinkList)malloc(sizeof(LNode));//生成新的结点 
 s->data=e;
 s->next=p->next;//插入L中 
 p->next=s;
 return OK;
}
Status ListDelete_L(LinkList &L,int i,ElemType &e){
 //在带头节点的单链线性表L中，删除第i个元素，并由e返回其值
 LinkList p,q;
 p=L;
 int j=0;
 while(p->next&&j<i-1)
 { //寻找第i个结点，并令p指向其前驱 
  p=p->next;
  ++j;
  } 
 if(!(p->next)||j>i-1) return ERROR;//删除位置不合理
 q=p->next;//q指向第i个结点 
 p->next=q->next;//令第i-1的结点直接与第i+1结点相连 
 e=q->data;
 free(q);
 return OK;  
}
void Length_Linklist(LinkList L){
 //求链表的长度 
 int num=0;
 LinkList p;
 p=L->next;
 while(p)
 {
  num++;
  p=p->next;
 }
 cout<<"链表的长度为："<<num; 
}
void Inverse_Linklist(LinkList &L){
 LinkList p,q,r;
 if(!L->next||!L->next->next) return ;//链表为空，或者只有一个结点 
 p=NULL;//新建只有头结点的链表
 q=L->next;//指向当前需逆置链表的第一个结点 
 while(q)
 {
  r=q->next;//先保存下一个结点的位置 
  q->next=p;//存到新的链表
  p=q;   
  q=r;
  } 
 L->next=p;//把旧链表的头结点指向新的尾 
}
//void MergeList_L(LinkList &La,LinkList &Lb,LinkList &Lc){
// //已知单链线性表La和Lb的元素按值非递减排列
// //归并La和Lb得到新的单链线性表Lc，Lc的元素也按值非递减排列
// LinkList pa,pb,r;
// pa=La->next;
// pb=Lb->next;
// Lc=pc=La;
// while(pa&&pb){
//  if(pa->data<=pb->data){
//   pc->next=pa;
//   pc=pa;
//   pa=pa->next;
//  }
// } 
//}

void menu(){
  cout<<endl;
     cout<<"*********************************"<<endl;
  cout<<"* 1.创建单链表                  *\n";
  cout<<"* 2.显示单链表                  *\n";
  cout<<"* 3.查找元素                    *\n";
  cout<<"* 4.插入元素（尾插法）          *\n";
  cout<<"* 5.删除元素                    *\n";
  cout<<"* 6.单链表的长度                *\n";
  cout<<"* 7.逆置                        *\n";
  //cout<<"* 8.有序表的合并                *\n";
  cout<<"* 0.退出                        *\n";
  cout<<"*********************************"<<endl;
  cout<<endl;
}

main.h

#include "com_def.h"
#include "linklist_def.h"
#include "linklist_func.h"
#include "menu.h"
using namespace std;
int main(){
 LinkList L;
 int choice=0;
 int i,n;
 ElemType e; 
 do{
  menu();
  cout<<"请输入你的选择:";
  cin>>choice;  
  switch(choice)
  {
   case 1:
    {
     if(Init_Linklist(L))
     {
      cout<<"单链表创建成功\n";
                  cout<<"链表为："<<endl;
                  OutputLinklist(L);
     }                 
              else
              {
               cout<<"单链表创建失败\n";
     }                 
              break;
    }
   case 2:
    {
     OutputLinklist(L);
     cout<<endl;
     break; 
    }
   case 3:
    {
     cout<<"请输入查找的位置:";
     cin>>i;
     if(GetElem(L, i, e))
     {
      cout<<"查找成功!"<<endl;
      cout<<"查找位置的值为:"<<e<<endl;
     }
     else
     {
      cout<<"查找失败!"<<endl;
     }     
     break;
    }
   case 4:
    {
     cout<<"请输入插入的位置:";
     cin>>i;
     cout<<"请输入插入的元素值:";
     cin>>e;
     if(Insert_Linklist(L, i, e))
     {
      cout<<"插入成功!\n";
                  cout<<"插入后的链表为："<<endl;
                  OutputLinklist(L);
     }                
              else
              {
               cout<<"插入失败!\n";
     }                
              break;
    }
   case 5:
    {
     cout<<"请输入要删除的位置:";
     cin>>i;       
     if(ListDelete_L(L, i, e))
     {
      cout<<"删除成功!\n";
      cout<<"删除元素的值为："<<e<<endl; 
                  cout<<"删除后的链表为："<<endl;
                  OutputLinklist(L);
     }                 
              else
              {
               cout<<"删除失败!\n";
     }                
              break;
    }
   case 6:
    {
     Length_Linklist(L);
     cout<<endl;
     break; 
    }
   case 7:
    {
     cout<<"逆置后的链表为："<<endl; 
     Inverse_Linklist(L);
     OutputLinklist(L);
     cout<<endl;
     break;
    }          
  }
 }while(choice!=0); 
}