线性表的顺序表示指的是用一组地址连续的存储单元依次存储线性表的数据元素.

  数据结构-线性表
 

//线性表的顺序表示指的是:用一组地址连续的存储单元依次存储线性表的数据元素.

   线性表的顺序存储结构是一种随机存取的存储结构。

1. 线性表:n个数据元素的有序集合。

 

线性表是一种常用的数据结构。在实际应用中,线性表都是以栈、队列、字符串、数组等特殊线性表的形式来使用的。由于这些特殊线性表都具有各自的特性,因此,掌握这些特殊线性表的特性,对于数据运算的可靠性和提高操作效率都是至关重要的。  线性表是一个线性结构,它是一个含有n≥0个结点的有限序列,对于其中的结点,有且仅有一个开始结点没有前驱但有一个后继结点,有且仅有一个终端结点没有后继但有一个前驱结点,其它的结点都有且仅有一个前驱和一个后继结点。

特征:

1.集合中必存在唯一的一个“第一元素”;
2.集合中必存在唯一的一个 “最后元素” ;
3.除最后一个元素之外,均有 唯一的后继(后件);
4.除第一个元素之外,均有 唯一的前驱(前件)。

Java中的List接口,就是线性表。ArrayList就是顺序线性表,LinkedList就是链表线性表。

 

//只要确定了存储线性表的起始位置,线性表中任一数据元素都可随机存取,

  

2. 线性表的顺序表示:ArrayList

 

一般使用数组(C语言中的数组采用顺序存储方式。即连续地址存储)来描述。

优点:在于随机访问元素,

缺点:插入和和删除的时候,需要移动大量的元素。

c语言实现代码:

 

[cpp] view
plain copy

 

 print?

  1. // Test.cpp : Defines the entry point for the console application.  
  2. //  
  3.   
  4. #include “stdafx.h”  
  5. #include <stdio.h>  
  6. #include “stdlib.h”  
  7. //宏定义  
  8. #define TRUE   1  
  9. #define FALSE   0  
  10. #define OK    1  
  11. #define ERROR   0  
  12. #define INFEASIBLE -1  
  13. #define OVERFLOW -2  
  14.   
  15. #define LT(a,b)   ((a)<(b))  
  16. #define N = 100         
  17.   
  18. #define LIST_INIT_SIZE 100 //线性表初始空间分配量  
  19. #define LISTINCREMENT   10 //线性表空间分配的增量  
  20.   
  21. typedef int Status;  
  22. typedef int ElemType;  
  23.   
  24. typedef struct LNode{  
  25.     ElemType  *elem;        //存储空间的基地址  
  26.     int      lenght;        //当前的长度  
  27.     int      listsize;      //当前分配的存储容量  
  28. }SqList;  
  29.   
  30. /** 
  31.  *构造空的线性表 
  32.  */  
  33.   
  34. Status initList(SqList &L, int lenght){  
  35.     if (lenght == 0) lenght = LIST_INIT_SIZE;  
  36.     L.elem = (ElemType *)malloc(lenght * sizeof(ElemType));  
  37.     if(!L.elem) exit(OVERFLOW);  //分配存储空间失败  
  38.     L.lenght = 0;                //初始空表长度为0  
  39.     L.listsize = lenght ;//初始存储容量为100  
  40.     return OK;  
  41. }  
  42. /************************************************************************/  
  43. /* 在第i位置插入e 
  44. */  
  45. /************************************************************************/  
  46. Status insertList(SqList &L, ElemType e, int i){  
  47.     ElemType *p,  *q;  
  48.     if(i<0 ||i > L.lenght) return ERROR;  //i值不合法  
  49.     if (L.lenght >= L.listsize) {  
  50.         ElemType *newbase = (ElemType *)realloc(L.elem ,(L.listsize +LISTINCREMENT)*sizeof(ElemType));  
  51.         if(!newbase) return OVERFLOW;   //存储分配失败    
  52.         L.elem = newbase;               //新基值  
  53.         L.listsize += LISTINCREMENT;    //增加存储容量  
  54.     }  
  55.     q = &L.elem[i];                     //q为插入的位置  
  56.     for (p = &L.elem[L.lenght]; p>=q; –p) {  
  57.         *p = *(p-1);                    //i元素之后的元素往后移动  
  58.     }  
  59.     *q = e;                             //插入e  
  60.     L.lenght +=1;  
  61.     return OK;  
  62.   
  63. }  
  64. /************************************************************************/  
  65. /* 快速排序  
  66. */  
  67. /************************************************************************/  
  68. void sortList(SqList &L){  
  69.       
  70.   
  71. }  
  72. /************************************************************************/  
  73. /* 删除第i位置元素,并用e返回其值                                                                     */  
  74. /************************************************************************/  
  75. Status deleteListElem(SqList &L, int i, ElemType &e){  
  76.     int *p,  *q;  
  77.     if(i<0 ||i > L.lenght) return ERROR;  //i值不合法  
  78.     q = &L.elem[i];                       //被删除元素的位置为i,L.elem就是数组名,  
  79.     e = *q;                               //被删除元素的值赋值给e  
  80.     for (p = q; p< (L.elem + L.lenght); p++){ //元素左移  
  81.         *p = *(p+1);  
  82.     }  
  83.     –L.lenght;  
  84.     return OK;  
  85. }  
  86.   
  87. /************************************************************************/  
  88. /*  快速排序 
  89. */  
  90. /************************************************************************/  
  91.   
  92. int partition(SqList &L, ElemType low, ElemType high){  
  93.     ElemType pivotkey = L.elem[low];               //枢轴记录关键字  
  94.     while (low < high) {                  //从表的两端向中间扫描  
  95.         while (low < high &&  L.elem[high] >= pivotkey ) –high;//高端位置扫描  
  96.         L.elem[low] = L.elem[high];     //交换数据,小于pivotkey移到低端  
  97.         L.elem[high] = pivotkey;  
  98.   
  99.         while (low < high && L.elem[low] <= pivotkey ) ++low;     //低端扫描  
  100.         L.elem[high] = L.elem[low];               //交换数据 大于pivotkey移到高端  
  101.         L.elem[low] = pivotkey;                                   
  102.     }  
  103.     return low;  
  104. }  
  105.   
  106. void quickSort(SqList &L, ElemType low, ElemType high){  
  107.     int pivot;  
  108.     if(low < high) {                                          
  109.         pivot =  partition(L,  low,  high);       
  110.         quickSort(L,  low,  pivot -1);          //低端子表排序  
  111.         quickSort(L,  pivot +1, high);          //高端子表排序  
  112.     }  
  113.       
  114. }  
  115.   
  116.   
  117. /************************************************************************/  
  118. /*  
  119. 合并两个线性表 
  120. */  
  121. /************************************************************************/  
  122.   
  123. void mergeList(SqList La, SqList Lb,  SqList &Lc){  
  124.     ElemType *pa, *pb, *pc;  
  125.     Lc.listsize =  La.lenght + Lb.lenght;  
  126.     initList(Lc, Lc.listsize);          //初始化LCpc = Lc.elem;  
  127.     Lc.lenght = Lc.listsize;  
  128.     pc = Lc.elem;  
  129.     pa = La.elem;  
  130.     pb = Lb.elem;  
  131.     while (pa <= &La.elem[La.lenght -1] && pb <= &Lb.elem[Lb.lenght -1]){  
  132.         if (*pa <= *pb) *pc++ = *pa++;  
  133.         else *pc++ = *pb++;  
  134.     }  
  135.     while(pa <= &La.elem[La.lenght -1]) *pc++ = *pa++; //插入La的剩余元素  
  136.     while(pb <= &Lb.elem[Lb.lenght -1]) *pc++ = *pb++; //插入Lb的剩余元素  
  137.   
  138. }  
  139.   
  140. /************************************************************************/  
  141. /* 打印list 
  142. */  
  143. /************************************************************************/  
  144. void printList(SqList L){  
  145.     printf(“当前值:”);   
  146.     for (int i =0; i<L.lenght;i++) {  
  147.         printf(“%d “, *(L.elem+i)); // L.elem为首地址  
  148.     }   
  149.     printf(“rn”);   
  150. }  
  151.   
  152. void main()  
  153. {  
  154.     SqList La,Lb,Lc;  
  155.     ElemType e;  
  156.     int init,i;  
  157.     init = initList(La, LIST_INIT_SIZE);  
  158.     int data[6] = {5,3,6,2,7,4};  
  159.     for (i=0; i<6;i++) {  
  160.         insertList(La,  data[i],  i);  
  161.     }  
  162.     printf(“LA:rn”);   
  163.     printList(La);  
  164.     deleteListElem(La, 3, e );  
  165.     printList(La);  
  166.     insertList(La,  e,  3);  
  167.     printList(La);  
  168.   
  169.     //排序  
  170.     quickSort(La,0, La.lenght-1);  
  171.     printList(La);  
  172.   
  173.     printf(“LB:rn”);   
  174.     initList(Lb, LIST_INIT_SIZE);  
  175.     int Bdata[5] = {1,3,2,4,6};  
  176.     for (i=0; i<5;i++) {  
  177.         insertList(Lb,  Bdata[i],  i);  
  178.     }  
  179.     //排序  
  180.     quickSort(Lb,0, Lb.lenght-1);  
  181.     printList(Lb);  
  182.   
  183.     mergeList(La, Lb,  Lc);  
  184.     printList(Lc);  
  185.   
  186. }  

 

 

 

 

//所以线性表的顺序表存储结构是一种随机存取的存储结构.

1.线性表的顺序存储结构

3. 线性表的链表表示LinkedList

一般使用链表来描述。

 

优点:对于新增和删除操作add和remove和方便。不需要移动元素。

缺点:不方便随机访问元素,LinkedList要移动指针

代码实现:

 

[cpp] view
plain copy

 

 print?

  1. // Test.cpp : Defines the entry point for the console application.  
  2. //  
  3. #include “stdafx.h”  
  4. #include <stdio.h>  
  5. #include “stdlib.h”  
  6. //宏定义  
  7. #define TRUE   1  
  8. #define FALSE   0  
  9. #define OK    1  
  10. #define ERROR   0  
  11. #define INFEASIBLE -1  
  12. #define OVERFLOW -2  
  13.   
  14. #define LT(a,b)   ((a)<(b))  
  15. #define N = 100         
  16.   
  17. typedef int Status;  
  18. typedef int ElemType;  
  19.   
  20. typedef struct LNode{  
  21.     ElemType  data;               
  22.     struct LNode   *next;     
  23. }LNode, *LinkList;  
  24.   
  25. /************************************************************************/  
  26. /* 
  27. 初始化链表 
  28. */  
  29. /************************************************************************/  
  30. Status initList(LinkList &L){  
  31.     /*单链表的初始化*/  
  32.     L = (LinkList)malloc(sizeof(LNode));    //申请一个头节点  
  33.     if(!L) exit(OVERFLOW);          //申请空间失败    
  34.     L->next=NULL;                //建立一个带都节点的空链表  
  35.     return OK;  
  36.   
  37.     /*  
  38.     需要改变指针的指针,所以参数必须是引用或者是 *L: 
  39.     (*L) = (Lnode *)malloc(sizeof(Lnode)); 
  40.     (*L)->next=NULL; 
  41.     return 1;                                                                      
  42.     */  
  43.   
  44. }  
  45.   
  46. /************************************************************************/  
  47. /*      
  48. 创建链表 
  49. */  
  50. /************************************************************************/  
  51. void createList(LinkList L, int n){  
  52.     /*单链表的初始化*/  
  53.     if (!L) {  
  54.         initList(L);  
  55.     }  
  56.     ElemType data;  
  57.     LinkList p,q = L;  
  58.     printf(“输入节点数据的个数%d:rn”, n);  
  59.     for(int i = 0; i<n; i++) {  
  60.         p = (LinkList) malloc( sizeof(LNode)); //申请一个新节点  
  61.         scanf(“%d”,&data);  
  62.         p->data = data;  
  63.         p->next = q->next;  
  64.         q->next = p;  
  65.         q = p;  
  66.     }  
  67. }  
  68. /************************************************************************/  
  69. /* 在第i位置插入e 
  70. */  
  71. /************************************************************************/  
  72. Status insertList(LinkList L, ElemType e, int i){  
  73.     LinkList s, p = L;  
  74.     int j = 0;  
  75.     while (p && j<i){                //寻找i节点  
  76.         p = p->next;  
  77.         j++;  
  78.     }  
  79.     if (!p ||j >i) return ERROR;  
  80.     s = (LinkList) malloc(sizeof(LNode));       //生成新节点  
  81.     s->data = e; s->next = p->next;            //插入L中  
  82.     p->next = s;  
  83.     return OK;  
  84.   
  85. }  
  86.   
  87. /************************************************************************/  
  88. /* 删除第i位置元素,并用e返回其值                                                                     */  
  89. /************************************************************************/  
  90. Status deleteListElem(LinkList L, int i, ElemType &e){  
  91.     LinkList p, q;  
  92.     int j = 0;  
  93.     p = L;  
  94.     while (p && j<i){  
  95.         p = p->next;  
  96.         ++j;  
  97.     }  
  98.     if (!p->next || j>i)  return ERROR;   //删除的位置不对  
  99.     q  = p->next; p->next = q->next;  
  100.     e = q->data; free(q);            //释放节点  
  101.     return OK;  
  102. }  
  103.   
  104.   
  105. /************************************************************************/    
  106. /*  插入排序  
  107. */    
  108. /************************************************************************/    
  109.   
  110. void  InsertSort(LinkList L)  
  111. {  
  112.     LinkList  list;             /*为原链表剩下用于直接插入排序的节点头指针*/  
  113.     LinkList  node;             /*插入节点*/  
  114.     LinkList  p;          
  115.     LinkList  q;          
  116.   
  117.     list = L->next;              /*原链表剩下用于直接插入排序的节点链表*/  
  118.     L->next = NULL;              /*只含有一个节点的链表的有序链表。*/  
  119.     while (list != NULL)   {    /*遍历剩下无序的链表*/  
  120.         node = list, q = L;     
  121.         while (q && node->data > q->data  ) {  
  122.             p = q;  
  123.             q = q->next;  
  124.         }  
  125.           
  126.         if (q == L) {  /*插在第一个节点之前*/  
  127.             L = node;  
  128.         }  else {     /*p是q的前驱*/  
  129.             p->next = node;     
  130.         }  
  131.         list = list->next;  
  132.         node->next = q; /*完成插入动作*/  
  133.   
  134.     }  
  135. }  
  136.   
  137.   
  138.   
  139. /************************************************************************/  
  140. /*  
  141. 合并两个线性表 
  142. */  
  143. /************************************************************************/  
  144.   
  145. void mergeList(LinkList  &La, LinkList  &Lb,  LinkList &Lc){  
  146.     LinkList pa, pb, pc;  
  147.     pa  = La->next;  
  148.     pb  = Lb->next;  
  149.     Lc =  pc = La;  
  150.     while (pa && pa) {  
  151.         if (pa->data > pb->data) {  
  152.             pc->next = pb;  
  153.             pc = pb;  
  154.             pb =pb->next;  
  155.         }else{  
  156.             pc->next = pa;  
  157.             pc = pa;   
  158.             pa =pa->next;  
  159.         }  
  160.     }  
  161.     pc->next = pa? pa :pb;  
  162.     free(Lb);  
  163. }  
  164.   
  165. /************************************************************************/  
  166. /* 打印list 
  167. */  
  168. /************************************************************************/  
  169. void printList(LinkList  L){  
  170.     printf(“当前值:”);  
  171.     LinkList p;  
  172.     p = L->next;  
  173.     while(p){  
  174.         printf(“%d “, p->data);   
  175.         p = p->next;  
  176.     }  
  177.     printf(“rn”);   
  178. }  
  179.   
  180. void main()  
  181. {  
  182.     LinkList  La,Lb,Lc;  
  183.     ElemType e;  
  184.     int init,i;  
  185.     printf(“LA:rn”);    
  186.     initList(La);  
  187.     createList(La, 5);  
  188.     insertList(La, 7,  3);    
  189.     printList(La);  
  190.     deleteListElem(La, 3,  e);    
  191.     printList(La);  
  192.     InsertSort(La);  
  193.     printList(La);  
  194.   
  195.     printf(“Lb:rn”);    
  196.     initList(Lb);  
  197.     createList(Lb, 4);  
  198.     InsertSort(Lb);  
  199.     printList(Lb);  
  200.   
  201.     printf(“Lc:rn”);   
  202.     initList(Lc);  
  203.     mergeList(La,   Lb,   Lc);  
  204.     printList(Lc);  
  205.   
  206. }   

#define OVERFLOW -1

 (1)//– – – – – -线性表的动态分配顺序存储结构- – – – –
typedef struct

#define TRUE 1

{elemtype *elem; //存储空间的基地址

#define FALSE 0

 int length;     //线性表的当前长度

#define OK 1

 int listsize;   //当前分配的存储容量(以sizeof(ElemType)为单位)

#define ERROR 0

}Sqlist;          //Sqlist指结构体的类型

#define NULL 0

 (2)//– – – – – -线性表的静态分配顺序存储结构- – – – –

#define LIST_INIT_SIZE 100   //线性表存储空间的初始分配量

typedef struct

#define LISTINCREMENT 10     //线性表存储空间的分配增量

{elemtype elem[max];

#include<iostream>

 int length;

#include<cstdio>

}sqlist;          //Sqlist指结构体的类型

using namespace std;

2.线性表的实现(建立、插入、删除)

typedef int Status;

//– – – – –静态– – – – – 

typedef int ElemType; 

 (1)在第i个元素前插入元素e

//—–线性表的动态分配顺序存储结构—–

Insertlist(Sqlist &L int i,elemtype e)

typedef struct

{int j;                                 

{

 if(i<1||i>L.length+1) printf(“ERROR”); // 位置不正确,出错

ElemType
*elem;  //存储空间基址

 else{for(j=L.length-1;j>i;j–)        

int length;
     //当前长度

      elem[j+1]=elem[j];                //
把第i个元素及后续元素向后移一位

int
listsize;    //当前分配的存储容量(以sizeof(ElemType)为单位)

      l.elem[i-1]=e;                    // 在第i个元素加入e

}SqList;

      L.length++;}                       //线性表长度加1

//1.初始化空表

 return L;

Status InitList_Sq(SqList &L)

}

{

 (2)删除第i个元素

//构造一个空的线性表L

delete(Sqlist &L,int i,elemtype &e)

L.elem =
(ElemType *)malloc(LIST_INIT_SIZE *sizeof(ElemType));

{int j;

if(!
L.elem) 

 if(j<1||j>L.length)return ERROR;

exit(OVERFLOW);     //存储分配失败  

 else{for(j=i;j<L.length;j++)         //
把第i+1个元素及后续元素向前移一位

L.length =
0;                      //空表长度为0

      L.elem[j-1]=L.elem[j];

L.listsize
= LIST_INIT_SIZE;       //初始存储容量

      L.length–;}                    //线性表长度减1

return OK;

 return L;

}//InitList_Sq

 }

//2.建立顺序表L

//– – – – –动态– – – – –

Status CreatList_Sq(SqList &L,int n) 

 (1)建立空线性表

{

Initlist(Sqlist L)

int i;    
    

{L.elem=(elemtype*)malloc(LIST_INIT_SIZE*sizeof(elemtype));//把分配的空间给基地址

ElemType e;

 if(!L.elem)exit(overflow);  // 存储分配失败

cout
<< “输入顺序表的长度:”;

 L.length=0;                  // 空表长度为0

cin
>> n;

 listsize=LIST_INIT_SIZE;        // 初始存储容量

L.length =
n;

}

if
(L.length > LIST_INIT_SIZE) 

 (2)在第i个元素前插入元素e

   L.elem
= (ElemType *) realloc(L.elem,L.length*sizeof(ElemType));

Insertlist(Sqlist &L int i,elemtype e)

cout<<“输入数据:”;

{                                 

for(i = 0;i
<= L.length-1;i++) 

 if(i<1||i>L.length+1) printf(“ERROR”); // 位置不正确,出错

{

 q=&(L.elem[i-1]);                      //插入的位置

scanf(“%d”,&e);   

 else{for(p=&(L.elem[L.length-1]);p>q;p–)        

L.elem[i]
= e; 

      *(p+1)=*p;                //
把插入位置的元素及后续元素向后移一位

}

      *q=e;                    // 在第i个元素加入e

return OK;

      L.length++;}              //线性表长度加1

}

 return L;

//3.销毁线性表

}

Status DestoryList_Sq(SqList &L)

 (3)删除第i个元素

{

delete(Sqlist &L,int i,elemtype &e)

//销毁线性表L

{

if
(L.elem) 

 if(j<1||j>L.length)return ERROR;

{

 p=&L.length[i-1];

free(L.elem); 

 e=*p;                           // 被删除元素的值赋给e

L.elem =
NULL; 

 q=L.elem+L.length;               //表尾元素的位置

        L.length = L.listsize = 0;

 else{for(++p;q<p;p++)        

return OK;

      *(p-1)=*p;                 //
把删除位置的元素及后续元素向前移一位

}

      L.length–;}               //线性表长度减1

return
ERROR;

 return L;

}

}

//4.重置空表

3.顺序表的合并

Status ClearList_Sq(SqList &L)

void MergeList_Sq(SqList La,SqList Lb,SqList &Lc){
    // 已知顺序线性表La和Lb的元素按值非递减排列
    // 归并La和Lb得到新的顺序线性表Lc,Lc的元素也按值非递减排列
    pa=La.elem; pb=Lb.elem;
    Lc.listsize=Lc.length=La.length+Lb.length;
    pc=Lc.elem=(ElemType
*)malloc(Lc.listsize*sizeof(ElemType));
    if(!Lc.elem) exit(OVERFLOW); //存储分配失败
    pa_last=La.elem+La.length-1;
    pb_last=Lb.elem+Lb.length-1;
    while(pa<=pa_last && pb<=pb_last){ //归并
        if(*pa<=*pb) *pc++=*pa++;
        else *pc++=*pb++;
    }
    while(pa<=pa_last) *pc++=*pa++; // 插入La的剩余元素
    while(pb<=pb_last) *pc++=*pb++; // 插入Lb的剩余元素
} // MergeList_Sq

{//将L重置为空表

L.length =
0;

cout
<< “Success!” <<endl;

return OK;

}

//5.判定是否空表

Status ListEmpty_Sq(SqList L) 

{//判定是否空表,若L为空表,则返回TRUE,否则返回FALSE

if
(L.length) 

return
ERROR;

return OK;

}

//6.求表长

int ListLength_Sq(SqList L)

{
//求L中数据元素的个数

return
L.length;

}

//7.取表第i个元素

Status GetElem_Sq(SqList L, int i, ElemType &e)

{
//用e返回顺序表L中第i个数据元素的值

//i的合法值为1 <= i <= ListLength_Sq(L)

if ((i <
1)||(i > L.length)) 

return
ERROR;  //i值不合法

else

e =
L.elem[i-1];

return OK;

}

//8.顺序表查找

int LocateElem_Sq(SqList L,ElemType e)

{
//在顺序线性表L中查找第1个值与e相等的元素的位序

//若找到,则返回其在L中的位序,否则返回0

int i = 1;

ElemType
*p;        //i的初值位第1个元素的位序

p =
L.elem;    //p的初值位第1个元素的存储位置  

while (i
<= L.length && L.elem[i] != e) 

i++;

if (i
<= L.length) 

return (i);

else 

return 0;

}//LocateElem_Sq

//9.求表L中元素的前驱

Status PriorElem_Sq(SqList L, ElemType cur_e, ElemType &pre_e)

{
//求表L中cur_e元素的前驱,用pre_e返回

int i;

cout
<< “输入特定元素值:”;

cin
>> cur_e;

i =
LocateElem_Sq(L,cur_e);

if (i <=
1) 

return
ERROR;  //i值不合法

pre_e =
L.elem[i-1];

cout
<< pre_e << endl;

return OK;

}

//10.求表L中元素的后继

Status NextElem_Sq(SqList L, ElemType cur_e, ElemType &next_e)

{
//求表L中cur_e元素的后继,用next_e返回

int i;

cout<<“输入特定元素值:”;

cin>>cur_e;

i=LocateElem_Sq(L,cur_e);

if
(i>=L.length) 

return
ERROR;  //i值不合法

next_e=L.elem[i + 1];

cout<<next_e << endl;

return OK;

}

//11.插入结点

Status ListInsert_Sq(SqList &L, int i, ElemType e)

{
//在顺序线性表L中第i个位置之前插入新的元素e

ElemType
*q,*p,*newbase;   //i的合法值为1<=i<=ListLength_Sq(L)+1

if(i < 1
|| i > L.length+1) 

return
ERROR;  //i值不合法

if
(L.length >= L.listsize)

{

//当前存储空间已满,增加分配

newbase =
(ElemType
*)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElemType));

if
(!newbase) exit(OVERFLOW);  //存储分配失败

L.elem =
newbase;                //新基址

L.listsize
+= LISTINCREMENT;     //增加存储容量

}

q =
&(L.elem[i-1]);               //q为插入位置

for (p =
&(L.elem[L.length – 1]);p >= q;–p) 

*(p+1) =
*p;  //插入位置及之后的元素后移

*q = e;  
        //插入e

++L.length;
    //表长增1

return OK;

}//ListInsert_Sq

//12.删除结点

Status ListDelete_Sq(SqList &L, int i, ElemType &e)

{
//在顺序线性表L中删除第i个元素,并用e返回其值

ElemType
*p,*q;

//i的合法值为1 <= i <= ListLength_Sq(L)

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;
                               //表长减1

    return OK;

}//ListDelete_Sq

//13.表遍历

Status ListTraverse(SqList L,Status(* visit)(ElemType e))

{ //遍历表.
依次对L的每个数据元素调用函数visit().一旦visit()失败,则操作失败.

int i;

for (i =
0;i <= L.length – 1;i++) 

{

(*
visit)(L.elem[i]); 

cout<<”  “;

}

cout<<endl;  

return OK;

}

//14.归并顺序表

void MergeList_Sq(SqList La,SqList Lb,SqList &Lc)

{
//已知顺序线性表La和Lb的元素按值非递减排列

//归并La和Lb得到新的顺序线性表Lc,Lc的元素也按值非递减排列

ElemType
*pa,*pb,*pc,*pa_last,*pb_last; 

pa =
La.elem;           

pb =
Lb.elem; 

Lc.listsize
= Lc.length = La.length + Lb.length;

pc =
Lc.elem = (ElemType *)malloc(Lc.listsize*sizeof(ElemType));

if
(!Lc.elem) 

exit(OVERFLOW);  //存储分配失败

pa_last =
La.elem + La.length – 1;

pb_last =
Lb.elem + Lb.length – 1;

while (pa
<= pa_last && pb <= pb_last)

{//归并

if (pa
<= pb) 

*pc++ =
*pa++;  

else 

*pc++ =
*pb++;

}

while (pa
<= pa_last) 

*pc++ =
*pa++;  //插入La的剩余元素

while (pb
<= pb_last) 

*pc++ =
*pb++;  //插入Lb的剩余元素

}//MergeList_Sq

//15.输出顺序表

void Output(SqList L)//输出线性表L 

{

     int i;

     for(i = 0;i < L.length;i++)

           printf(“%d “,L.elem[i]);

     printf(“n”);

//16.对顺序表数据元素按升序排列

int SortInc(SqList &L)

{

//用冒泡法排序

int temp;

for(int i =
0;i < L.length – 1;i++)

for(int j =
i;j < L.length;j++)

{

if(L.elem[i] > L.elem[j])

{

temp =
L.elem[i];

L.elem[i]
= L.elem[j];

L.elem[j]
= temp;

}

}

return 0;

}

//17.对顺序表数据元素按降序排列

int SortDec(SqList &L)

{

//用冒泡法排序

int temp;

for(int i =
L.length – 1;i > 0;i–)

for(int j =
i;j >= 0 ;j–)

{

if(L.elem[i] > L.elem[j])

{

temp =
L.elem[i];

L.elem[i]
= L.elem[j];

L.elem[j]
= temp;

}

}

return 0;

}

//18.将一个顺序表逆置

int Inversion_Sq(SqList &L)

{

int i,temp;

for(i = 0;i
< L.length/2;i++)

{

temp =
L.elem[i];

L.elem[i]
= L.elem[L.length – i – 1];

L.elem[L.length-i-1] = temp;

}

return 1;

}

void output()//窗口边框

{

     int i;

     for(i = 0;i < 10;i ++)

        printf(” “);

     for(i = 0;i < 31;i ++)

        printf(“*”);

     printf(“n”);

}

void mainpp()//显示窗口

{

     int i;

     output();

     for(i = 0;i < 10;i ++)

        printf(” “);

        printf(“*   “);

     printf(“1.建立一个顺序表”);

     for(i = 0;i < 10;i++)

        printf(” “);

        printf(“*”);

        printf(“n”); 

     for(i = 0;i < 10;i ++)

        printf(” “);

        printf(“*   “);

     printf(“2.输出一个顺序表”);

     for(i = 0;i < 10;i++)

        printf(” “);

        printf(“*”);

        printf(“n”); 

     for(i = 0;i < 10;i ++)

        printf(” “);

        printf(“*   “);

     printf(“3.在顺序表中查找”);

     for(i = 0;i < 10;i ++)

        printf(” “);

        printf(“*”);

        printf(“n”);

     for(i = 0;i < 10;i ++)

        printf(” “);

        printf(“*   “);

     printf(“4.向顺序表中插入一个元素”);

     for(i = 0;i < 2;i++)

        printf(” “);

        printf(“*”);

        printf(“n”); 

     for(i = 0;i < 10;i ++)

        printf(” “);

        printf(“*   “);

     printf(“5.删除顺序表中的一个元素”);

     for(i = 0;i < 2;i++)

        printf(” “);

        printf(“*”);

        printf(“n”); 

     for(i = 0;i < 10;i++)

        printf(” “);

        printf(“*   “);

     printf(“6.从顺序表中取出一个元素”);

     for(i = 0;i < 2;i++)

        printf(” “);

        printf(“*”);

        printf(“n”); 

     for(i = 0;i < 10;i++)

        printf(” “);

        printf(“*   “);

     printf(“7.将两个顺序表合并”);

     for(i = 0;i < 8;i++)

        printf(” “);

        printf(“*”);

        printf(“n”); 

     for(i = 0;i < 10;i++)

        printf(” “);

        printf(“*   “);

printf(“8.比较两个顺序表的大小”);

     for(i = 0;i < 4;i++)

        printf(” “);

        printf(“*”);

        printf(“n”); 

     for(i = 0;i < 10;i++)

        printf(” “);

        printf(“*   “);

printf(“9.将顺序表逆置”);

     for(i = 0;i < 12;i++)

        printf(” “);

        printf(“*”);

        printf(“n”); 

     for(i = 0;i < 10;i++)

        printf(” “);

        printf(“*   “);

printf(“10.将顺序表中升序排序”);

     for(i = 0;i < 5;i++)

        printf(” “);

        printf(“*”);

        printf(“n”); 

     for(i = 0;i < 10;i++)

        printf(” “);

        printf(“*   “);

printf(“11.将顺序表中降序排序”);

     for(i = 0;i < 5;i++)

        printf(” “);

        printf(“*”);

        printf(“n”); 

     for(i = 0;i < 10;i++)

        printf(” “);

        printf(“*   “);

printf(“12.判断顺序表中是否为空”);

     for(i = 0;i < 3;i++)

        printf(” “);

        printf(“*”);

        printf(“n”); 

     for(i = 0;i < 10;i++)

        printf(” “);

        printf(“*   “);

printf(“13.求表L中元素的前驱”);

     for(i = 0;i < 6;i++)

        printf(” “);

        printf(“*”);

        printf(“n”); 

     for(i = 0;i < 10;i++)

        printf(” “);

        printf(“*   “);

printf(“14.求表L中元素的后驱”);

     for(i = 0;i < 6;i++)

        printf(” “);

        printf(“*”);

        printf(“n”); 

     for(i = 0;i < 10;i++)

        printf(” “);

        printf(“*   “);

printf(“15.销毁线性表”);

     for(i = 0;i < 13;i++)

        printf(” “);

        printf(“*”);

        printf(“n”); 

     for(i = 0;i < 10;i++)

        printf(” “);

        printf(“*   “);

printf(“16.重置顺序表”);

     for(i = 0;i < 13;i++)

        printf(” “);

        printf(“*”);

        printf(“n”); 

     for(i = 0;i < 10;i++)

        printf(” “);

        printf(“*   “);

     printf(“0.退           出 “); 

     for(i = 0;i < 8;i++)

        printf(” “);

        printf(“*”);

        printf(“n”); 

     output(); 

}

int main()//主函数

{

     int n = 0,i,j = 0,k = 1,m,p,q,x,y,e,cur_e = 0,pre_e = 0,next_e;

     SqList l,la,lc;

     InitList_Sq(l);

     mainpp();

     while(k) 

     {

           printf(“请选择0–16:”);

           scanf(“%d”,&m);

           getchar();

           switch(m)

           {

                  case 0:exit(0);

                  case 1:{

                       CreatList_Sq(l,n);

                       Output(l);

                       break;

                       }  

                  case 2:Output(l);printf(“n”);break;

                  case 3:{

                       printf(“请输入要查找的元素值:”);

                       scanf(“%d”,&x);

                       j = LocateElem_Sq(l,x) + 1;

                       printf(“要查找的元素的位序:%dn”,j);

                       printf(“n”);

                       break;

                       }

                  case 4:{

                       printf(“请输入要插入的元素的位置及其值:”);

                       fflush(stdin);

                       scanf(“%d”,&i);

                       scanf(“%d”,&x);

                       ListInsert_Sq(l,i,x);

                       Output(l);

                       printf(“n”);

                       break;

                       }

                  case 5:{

                       printf(“请输入要删除元素的位置:”);

                       fflush(stdin);

                       scanf(“%d”,&i);

                       ListDelete_Sq(l,i,y); 

                       Output(l);

                       printf(“n”);

                       break;

                       }

                  case 6:{

                       printf(“请输入要取出的元素的序号:”);

                       fflush(stdin);

                       scanf(“%d”,&i);

                       GetElem_Sq(l,i,e);

                       printf(“取出的第%d个元素为:%dn”,i,e);

                       break;

                       }

                  case 7:{

                       InitList_Sq(la);

 
InitList_Sq(lc);

                       printf(“请输入第2个顺序表元素的个数: n”);

 
printf(“输入元素值,构建顺序表:n”);

                       scanf(“%d”,&m);

                       CreatList_Sq(la,m);

 
printf(“n新建的顺序表为:n”);

                       Output(la);

                       MergeList_Sq(l,la,lc); 

                       printf(“输出合并后的顺序表中的元素:n”);

                       Output(lc);

                       break;

                       }

 case 8:{

                       InitList_Sq(la);

                       printf(“请输入第2个顺序表元素的个数: n”);

 
printf(“输入元素值,构建顺序表:n”);

                       scanf(“%d”,&m);

                       CreatList_Sq(la,m);

 
printf(“n新建的顺序表为:n”);

                       Output(la);

  if(p ==
1)

 
printf(“l > la”);

  else
if(p == -1)

 
printf(“l < la”);

  else 

 
printf(“l == la”);

                       break;

                       }

 case 9:{

 Inversion_Sq(l);

                      Output(l);

                      printf(“n”);

                      break;

                      }

 case 10:{

 SortInc(l);

                      Output(l);

                      printf(“n”);

                      break;

                      }

 case 11:{

 SortDec(l);

                      Output(l);

                      printf(“n”);

                      break;

                      }

 case 12:{

 q =
ListEmpty_Sq(l);

 if(q ==
1)

 printf(“此表为空”);

 else

   
 printf(“此表不空”);

                      printf(“n”);

                      break;

                      }

 case 13:

 {

 PriorElem_Sq(l,cur_e,pre_e);

 break;

 }

 case 14:

 {

 NextElem_Sq(l,cur_e,next_e);

 break;

 }

 case 15:

 {

 DestoryList_Sq(l);

 break;

 }

 case 16:

 {

 ClearList_Sq(l);

 break;

 }

                  default :exit(0);

           }  

           printf(“继续运行吗?Y(1)/N(0):”);

           scanf(“%d”,&k);

           if(!k)

           exit(0); 

     } 

return 0;