线性表的基本操作

一、实验目的

1．掌握用 C++/C 语言调试程序的基本方法。

2．掌握线性表的顺序存储和链式存储的基本运算，如插入、删除等。

二、实验要求

1. C++/C完成算法设计和程序设计并上机调试通过。 2．撰写实验报告，提供实验结果和数据。 3. 分析算法，要求给出具体的算法分析结果，包括时间复杂度和空间复杂度，并简要 给出算法设计小结和心得。

三、实验内容：

1. 分析并运行以下各子程序的主要功能。 程序 1 ：顺序存储的线性表和运算 #include<>

#define MAXSIZE 100 int list[MAXSIZE]; int n;

/*insert in a seqlist*/

int sq_insert(int list[], int *p_n, int i, int x)

{int j;

if (i<0 || i>*p_n) return(1);

if (*p_n==MAXSIZE) return(2); for (j=*p_n+1; j>i; j--)

list[j]=list[j-1]; list[i]=x; (*p_n)++; return(0);

}

/*delete in a seq list*/

int sq_delete(int list[], int *p_n, int i)

{int j;

if (i<0 || i>=*p_n) return(1); for (j = i+1; j<=*p_n; j++) list[j-1] = list[j]; (*p_n)--; return(0);

}

void main()

{int i,x,temp;

printf(\"please input the number for n\\n\"); printf(\"n=\"); scanf(\"%d\for (i=0; i<=n; i++)

{printf(\"list[%d]=\scanf(\"%d\

printf(\"The list before insertion is\\n\"); for (i=0; i<=n; i++) printf(\"%d \printf(\"\\n\");

printf(\"please input the position where you want to insert a value\\nposition=\"); scanf(\"%d\

printf(\"please input the value you want to insert.\\nx=\"); scanf(\"%demp=sq_insert(list,&n,i,x);

switch(temp)

{case 0:printf(\"The insertion is successful!\\n\"); printf(\"The list is after insertion is\\n\");

for(i=0; i<=n; i++) printf(\"%d \printf(\"%d\\n\case 1:

case 2:printf(\"The insertion is not successful!\\n\");break;} /*deleting*/

printf(\"The list before deleting is\\n\"); for (i=0; i<=n; i++) printf(\"%d \printf(\"\\n\");

printf(\"please input the position where you want to delete a value\\nposition=\"); scanf(\"%d\

temp=sq_delete(list,&n,i); switch(temp)

{case 0:printf(\"The deleting is successful!\\n\"); printf(\"The list is after deleting is\\n\");

for(i=0; i<=n; i++) printf(\"%d \printf(\"%d\break;

case 1:printf(\"The deleting is not successful!\");break;}

}

2. 分析并运行以下各子程序的主要功能。

程序 2 链式存储的线性表和运算 #include<> #include<> struct node{

char data;

struct node *next;

}; typedef struct node NODE; /*This function creates a link_list with N nodes.*/ NODE *create_link_list(int n)

{int i;

NODE *head, *p, *q; if (n==0) return NULL; head = (NODE *) malloc(sizeof(NODE));

p = head; printf(\"Please input %d chars for the link list\\n\

{scanf(\"%c \printf(\"test3\\n\"); p->next=q; p=q;} scanf(\"%c \p->next=NULL; return (head);}

/*This function inserts a node whose value is b*/ /*before the node whose value is a, if the node is not exist,*/ /*then insert it at the end of the list*/ void insert(NODE **p_head, char a, char b)

{NODE *p, *q; q = (NODE *)malloc(sizeof(NODE)); q->data = b; q->next =NULL;

if (* p_head == NULL) * p_head = q; else

{p=(NODE*)malloc(sizeof(NODE)); p = * p_head;

while (p->data != a && p->next != NULL) p = p->next; q->next = p->next; p->next = q;}

}

/*The function deletes the node whose value is a,*/ /*if success, return 0, or return 1*/ int deletenode(NODE **p_head, char a)

{NODE *p, *q; q=*p_head; if (q==NULL) return(1); if (q->data == a)

{* p_head = q->next; free(q);

return (0);} else

{while (q->data != a && q->next != NULL) {p = q;

q = q->next;} if (q->data == a) {p->next = q->next; free(q); return(0);}

else return(1);} } void main() { NODE *my_head,*p; /* create a link list with m nodes */ int m;

char ch_a,ch_b; printf(\"please input the number of nodes for the link_list\\nm=\"); scanf(\"%d\

getchar(); printf(\"test1\\n\");

my_head = (NODE *) malloc(sizeof(NODE));

my_head=create_link_list(m); /*Output the link list*/ printf(\"The link list is like:\\n\"); p=my_head; while (p != NULL) {printf(\"%c \} printf(\"\\n\");

/*insert a node whose value is b before a*/ printf(\"Please input the position for a\\n ch_a=\"); getchar(); scanf(\"%c\getchar();

printf(\"Please input the value that you want to insert\\n ch_b=\"); scanf(\"%c\getchar(); insert(&my_head,ch_a,ch_b); printf(\"The link list after insertion is like:\\n\"); p=my_head;

while (p != NULL)

{printf(\"%c \

} printf(\"\\n\"); /*delete a node whose value is a*/ printf(\"Please input the position for a a=\"); scanf(\"%c\deletenode(&my_head,ch_a);

printf(\"The link list after deleting is like:\\n\"); p=my_head; while (p != NULL)

{printf(\"%c \

} printf(\"\\n\");

}

3. 运行以下程序并分析各子函数的主要功能。 #include <> #include <> struct tagNode

{

int data; struct tagNode *pNext; };

typedef struct tagNode* pNode;

// 将结点插入到链表的适当位置，这是一个降序排列的链表

//

void insertList(pNode head,// 链表头结点

pNode pnode)// 要插入的结点

{

pNode pPri=head;

while (pPri->pNext!=NULL)

{

if (pPri->pNext->datadata)

{

pnode->pNext=pPri->pNext; pPri->pNext=pnode; break;

}

pPri=pPri->pNext;

}

if (pPri->pNext==NULL)// 如果要插入的结点最小

{

pPri->pNext=pnode;

}

}

// 输出链表

void printLinkedList(pNode head)

{

pNode temp=head->pNext; while (temp!=NULL)

{

printf(\"%d \

}

}

// 从链表中删除结点

void delformList(pNode head,int data)

{

pNode temp=head->pNext; pNode pPri=head; while (temp!=NULL)

{

if (temp->data==data)

{

pPri->pNext=temp->pNext; free(temp); break;

pPri=temp;

temp=temp->pNext;

}

}

void main()

{

pNode head=(pNode)malloc(sizeof(struct tagNode));// 给头指针分配空间 pNode pTemp=NULL;

int temp; head->pNext=NULL;// 比较好的习惯就是分配好空间，马上赋值 printf(\" 请输入要放入链表中的数据，以 -1结尾： \");

// 读入数据，以 -1结尾，把数据插入链表中 scanf(\"%d\while (temp!=-1)

{

pTemp=(pNode)malloc(sizeof(struct tagNode)); pTemp->data=temp;

pTemp->pNext=NULL;

insertList(head,pTemp); scanf(\"%d\

}

printf(\" 降序排列的链表为： \\n\"); printLinkedList(head); printf(\"\\n\");

// 下面的代码当删除函数编写成功后， 可以取消注释， 让其执行 ,主要是调用函数实现链表结 点的删除

//printf(\" 请输入要删除数，以 -1结尾： \"); //scanf(\"%d\//while (temp!=-1) //{

// delformList(head,temp); // scanf(\"%d\//}

//printf(\" 删除节点后，链表中剩余数据为： \"); //printLinkedList(head); //printf(\"\\n\");

}

四、思考与提高

试将以上链表改为有序表，并分析有序表有哪些显著的优点和缺点 库函数载和常量定义：（代码 ,C++） #include using namespace std; const int MaxSize=100;

(1)

datatype> class SeqList

{

顺序表存储结构的定义 (类的声明 )：(代码) template public:

SeqList( ); // 无参构造函数 SeqList(datatype a[ ], int n); // 有参构造函数 ~SeqList(){}; // 析构函数为空 int Length(); // 求线性表的长度 datatype Get(int i); // 按位查找，取线性表的第 i 个元素 int Locate(datatype item); // 查找元素 item

void Insert(int i, datatype item); // 在第 i 个位置插入元素 item datatype Delete(int i); // 删除线性表的第 i 个元素 void display(); // 遍历线性表，按序号依次输出各元素 private:

datatype data[MaxSize]; // 存放数据元素的数组 int length; // 线性表的长度 };

（2）初始化顺序表算法实现（不带参数的构造函数） /* * 输 入：无

*前置条件：顺序表不存在 * 功 能：构建一个顺序表 * 输 出：无

* 后置条件：表长为 0 */

实现代码：

template

SeqList:: SeqList（ ）

{

length=0;

}

（3）顺序表的建立算法（带参数的构造函数） /*

* 输 入：顺序表信息的数组形式 a[], 顺序表长度 n *前置条件：顺序表不存在 *功 能：将数组 a[] 中元素建为长度为 n 的顺序表 * 输 出：无

*后置条件：构建一个顺序表 */

实现代码：

template

SeqList:: SeqList（datatype a[], int n）

if (n>MaxSize)

{ cout<<\" 数组元素个数不合法 \"<}

for (int i=0; i} ( 4)在顺序表的第 i 个位置前插入元素 e 算法 /* *输 入：插入元素e,插入位置i *前置条件：顺序表存在， i 要合法 *功 能:将元素e插入到顺序表中位置i处 * 输 出：无

*后置条件：顺序表插入新元素，表长加 1 */

实现代码： template void SeqList::Insert(int i, datatype item) {

int j;

if (length>=MaxSize) {

cout<<\"溢出\"<}

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

{ cout<<\"i 不合法！ \"<} for (j=length; j>=i; j--) data[j]=data[j-1]; data[i-1]=item; length++; } (5)删除线性表中第i个元素算法 /* *输 入：要删除元素位置 i

*前置条件：顺序表存在 ,i 要合法 *功 能：删除顺序表中位置为 i 的元素 *输 出：无 *后置条件： 顺序表册除了一个元素，表长减 1 */

实现代码： template datatype SeqList::Delete(int i)

{

int item,j;

if (length==0) {

cout<<\" 表为空 ,无法删除元素 !\"<}

if (i<1 || i>length) {

cout<<\"i 不合法 !\"<}

item=data[i-1];// 获得要删除的元素值 for (j=i; jdata[j-1]=data[j]; // 注意数组下标从 0 记 length--; return item;

}(6)遍历线性表元素算法 /* * 输 入：无

*前置条件：顺序表存在 * 功 能：顺序表遍历 * 输 出：输出所有元素 *后置条件：无

*/ 实现代码： template void SeqList::display() { if(length==0)

{

cout<<\" 表为空，无法输出 !\"<for(int i=0;i}

}

(7) 获得线性表长度算法 /* * 输 入：无

*前置条件：顺序表存在 * 功 能：输出顺序表长度 * 输 出：顺序表长度 *后置条件：无

*/ 实现代码： template int SeqList::Length() { return Length;

}

(8) 在顺序线性表中查找 e 值，返回该元素的位序算法 /* * 输 入：查询元素值 e *前置条件：顺序表存在 * 功 能：按值查找值的元素并输出位置 * 输 出：查询元素的位置 *后置条件：无 */

实现代码：

template

int SeqList::Locate(datatype item)

{

for (int i=0; iif (data[i]==item) return i+1 ;

// 下标为 i 的元素等于 item ，返回其序号 return 0; // 查找失败

i+1

(9) 获得顺序线性表第 i 个元素的值 /*

* 输 入：查询元素位置 i

*前置条件：顺序表存在， i 要合法

* 功 能：按位查找位置为 i 的元素并输出值 * 输 出：查询元素的值 *后置条件：无 */

实现代码：

template

datatype SeqList::Get(int i)

{

if (i<0||i>length)

{

cout<<\"i 不合法 !\"<}

else return data[i-1];

}

(10) 判表空算法 /*

* 输 入：无 *前置条件：无

* 功 能：判表是否为空

* 输 出：为空返回 1，不为空返回 0 *后置条件：无

*/ 实现代码： template bool SeqList::Empty()

{

if (length==0) { return 1;

}

else

{ return 0;

}

}

(11) 求直接前驱结点算法 /* *输 入：要查找的元素 e,待存放前驱结点值 el * 前置条件：无 *功 能：查找该元素的所在位置,获得其前驱所在位置。 *输 出：返回其前驱结点的位序。 *后置条件： e1 值为前驱结点的值 */

实现代码：

template

int SeqList::Pre(datatype item)

int k=Locate(item)-1; if (k>0)

return k; else

{

cout<<\" 无前驱结点！ \"<}

}

(12) 求直接后继结点算法 /* *输 入：要查找的元素 e,待存放后继结点值 el * 前置条件：无 *功 能：查找该元素的所在位置,获得其后继所在位置。 *输 出：返回其后继结点的位序。 *后置条件： e1 值为后继结点的值 */

实现代码： template int SeqList::Suc(datatype item)

{

int k=Locate(item)+1; if (k>length)

{

cout<<\" 无后继结点 !\"<}

else

{

return k;

}

}

上机实现以上基本操作,写出 main() 程序： 用以上基本操作算法,实现 A=AUB 算法。板实现) /*

*输 入：集合A,集合B * 前置条件：无

* 功 能：实现 A=AUB * 输 出：无

* 后置条件： A 中添加了 B 中的元素。 */

实现代码：

template

SeqList SeqList::Add(SeqList& item) {

if ())

return *this; else

{

int k=();

int num=this->Length(); for (int i=1;i<=k;i++)

for(int j=0;j利用函数模(if (data[j]==(i))

{

break;

}

else if (num-1==j&&data[num-1]!=(i))

{

this->Insert(++num,(i));

}

}

return *this;

}

}

void main()

{

SeqList A,B;

cout<<\"A U B 的结果是:\"<cout<}

实现代码：

template

void SeqList::orderInsert(datatype item)

{

int num=this->Length(); for (int i=0;i{

if ((data[i]item))

{

for (int k=num;k>i;k--) data[k]=data[k-1]; data[i+1]=item; length++; break;

}

if (data[i]>item)

{

for(int k=num;k>i;k--) data[k]=data[k-1]; data[i]=item; length++; break;

}

}

}

void main()

SeqList A,B;

(1,3) ; (2,5); (3,6) ; (4,8) ; (5,10) ; // 插入顺序表 cout<<\" 原顺序表为 :\"<(4); // 插入元素

cout<<\" 插入新元素后的顺序表为 :\"<}

算法实现：La,Lb为非递减的有序线性表，将其归并为 删除一重复值) (利用函数类板实现) MergeList ： /* *输 入：有序线性表La 有序线性表Lb * 前置条件：顺序表已有序 *功 能：将两线性表归并，不去掉相同元素 * 输 出： 返回一个新的有序线性表 Lc * 后置条件：无 */

实现代码：

Lc,该线性表仍有序(未考虑相同时

templateSeqList SeqList::ElseAdd(SeqList Seq1,SeqList Seq2) {

int num=();

for(int i=0;i<=num;i++){

(i));

}

return Seq1;

}

void main()

{

SeqList La,Lb,Lc; (1,2) ; (2,4) ; (3,6) ;

(4.8) ; // 插入 La

cout<<\"La 中元素为 :\"<(3.8) ; //插入 Lb

cout<<\"Lb 中元素为 :\"<Lc=(La,Lb); //合并两线性表 cout<<\"合并后的 Lc为:\"<