期末复习之数据结构第2章线性表

henu_Newxc03

发布于 2021-12-28 12:38:01

6040

发布于 2021-12-28 12:38:01

文章被收录于专栏：Newxc03的前端之路

一.课本知识点

1.线性结构

定义：若结构是非空有限集，则有且仅有一个开始结点和一个终端结点，并且所有结点都最多只有一个直接前趋和一个直接后继。
可表示为：（a1 , a2 , ……, an）是一个有序（次序）集。 特点： ① 只有一个首结点和尾结点； ② 除首尾结点外，其他结点只有一个直接前驱和一个直接后继。 简言之，线性结构反映结点间的逻辑关系是一对一的。

2.线性表

例子：

//伪代码
void union(List &La, List Lb) {
    La_len = ListLength(La);    // 求线性表La的长度
    Lb_len = ListLength(Lb);   // 求线性表Lb的长度
    for(i=1;i<=Lb_len; i++) {
        GetElem(Lb, i, e); // 取Lb中第i个数据元素赋给e
        if (!LocateElem ( La, e, equal( )) ) 
            ListInsert(La, ++La_len, e);
              // La中不存在和 e 相同的数据元素，则插入之
        }//for
} // union

3.线性表的顺序表示

线性表的顺序表示又称为顺序存储结构或顺序映像。
顺序存储定义：把逻辑上相邻的数据元素存储在物理上相邻的存储单元中的存储结构。 简言之，逻辑上相邻，物理上也相邻
顺序存储方法：用一组地址连续的存储单元依次存储线性表的元素，可通过数组V[n]来实现。
顺序表的特点：

逻辑上相邻的数据元素，其物理上也相邻；
若已知表中首元素在存储器中的位置，则其他元素存放位置亦可求出（利用数组下标）。计算方法是（参见存储结构示意图）：设首元素a1的存放地址为LOC(a1)（称为首地址），设每个元素占用存储空间（地址长度）为L字节，则表中任一数据元素的存放地址为： LOC(ai+1) = LOC(ai)+L LOC(ai) = LOC(a1) + L *（i-1）

顺序表的存储结构示意图：

注意：

4.顺序表的基本操作

线性表的动态分配顺序存储结构:

# define  LIST_INIT_SIZE   100       //符号常量   // 线性表存储空间的初始分配量
# define   LISTINCREMENT    10     // 线性表存储空间的分配增量
typedef struct {                                    //typedef 给结构类型起别名
       ElemType *elem;                          //表基址
       int                length;                      //表长（特指元素个数）
       int                listsize;                     //表当前存储容量
}SqList

线性表的清空操作:

Status ClearList(Sqlist &L)
{
    if(L.elem==NULL)
        exit(ERROR);
    int i;
    ElemType *p_elem = L.elem;
    for(i = 0;i < L.length;i++){
        *L.elem = NULL;
        L.elem++;
    }
    L.elem = p_elem;
    L.length = 0;
    return OK;
}

线性表的求长度操作:

Status ListLength(SqList  L)
{
	 return L.length;
}

线性表元素的修改操作：

status modify(SqList &L, int i, ElemType e){ //注意：i是位置		
		if (i<1 || i>L.length) //判断位置i是否合法
        return ERROR;
        L.elem[i-1]=e; //或者 *(L.elem+i-1)=e	
        return OK;
}

线性表元素的插入操作：

Status ListInsert_Sq(SqList &L,int i, ElemType e){
    if(i<1 || i>L.length+1) return ERROR
    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
    }
}

5.线性表的链式表示

链式存储特点：逻辑上相邻，物理上不一定相邻
链表存放示意图：

每个存储结点都包含两部分：数据域和指针域(链域) 。
在单链表中，除了首元结点外，任一结点的存储位置由其直接前驱结点的链域的值指示。
与链式存储有关的术语

何谓头指针、头结点和首元结点？

如何表示空表？

头结点的数据域内装的是什么?

循环链表：表中最后一个结点的指针域指向头结点，整个链表形成一个环。

双向链表：结点有两个指针域，一个指向直接前驱，一个指向直接后继。

6.链表的基本操作

单链表的读取(或修改）

Status GetElem_L(LinkList L, int i, ElemType &e){
// 注意：L为带头结点的单链表的头指针
// 当第i个元素存在时,其值赋给e并返回OK,否则返回ERROR
     P=L->next;      
     j=1;//j用来计数
     while(p && j<i)  {p=p->next;    ++j;}
     if (!p || j>i)   return ERROR;
//!p即p为空，有两种情况，第一种是表为空；第二种是i的值超过了表的长度，while循环执行完后p走到最后一个元素还没有找到i的位置。j >i 就是i是0或者负数的情况。
     e=p->data;
     return OK;
}

单链表的删除

Status ListDelete_L(LinkList &L,int i,ElemType &e){
		p=L; j=0;
		while(p->next && j<i-1){p=p->next;++j}
		if(!p->next || j>i-1) return ERROR;
		//p指向第i-1个结点
		//判断p->next ，是要保证p的后面还有结点。
		q=p->next; 
		e=q->data; 
		p->next=q->next;
		free(q)
          return OK;
	}

单链表的遍历

void travle(LinkList L){
	LinkList p
	cout<<"建立的链表为：";
	for(p=L->next;p!=NULL;p=p->next)
		cout<<p->data<<"  ";
	}

二.练习题

题组一：

题组二：

一、填空 1. 在顺序表中插入或删除一个元素，需要平均移动 n/2或n-1/2 元素，具体移动的元素个数 与 插入或删除元素的位置 有关。 2. 向一个长度为n的向量的第i个元素(1≤i≤n+1)之前插入一个元素时，需向后移动 n-i+1 个元素。 3. 向一个长度为n的向量中删除第i个元素(1≤i≤n)时，需向前移动 n-i 个元素。 4. 在单链表中，除了首元结点外，任一结点的存储位置由 前驱结点的后继指针 指示。 二、简答题 1. 试比较顺序存储结构和链式存储结构的优缺点。在什么情况下用顺序表比链表好？ 顺序表优点：存储密度大存储空间利用率高 缺点：插入或删除元素时不方便 链式存储优点：插入或删除元素时很方便 缺点:存储密度小存储空间利用率低 在插入和删除情况比较少的情况下用顺序表比链表好 2 . 描述以下三个概念的区别：头指针、头结点、首元结点（第一个元素结点）。在单链表中设置头结点的作用是什么？ 头指针：指向链表第一个结点的指针 头节点：在首元结点之前附设的一个结点，该结点不存储数据元素，其指针指向首元节点，其作用主要是为了方便对链表的操作 首元结点：链表中存储第一个数据元素的结点 三、线性表具有两种存储方式，即顺序方式和链接方式。现有一个具有五个元素的线性表L={23，17，47，05，31}，若它以链接方式存储在下列100～119号地址空间中，每个结点由数据（占2个字节）和指针（占2个字节）组成，如下所示： 05 U 17 X 23 V 31 Y 47 Z ^ ^ 100 120 其中指针X，Y，Z的值分别为多少？该线性表的首结点起始地址为多少？末结点的起始地址为多少？ X:116 Y:NULL Z:100 首结点起始地址108 末结点起始地址为112 四、编程题 1. 写出在顺序存储结构下将线性表逆转的算法，要求使用最少的附加空间。 void Reverse(SqList& L) { for (int i = 0; i <= (L.length - 1) / 2; i++) { int temp = L.data[i]; L.data[i] = L.data[length - 1-i]; L.data[length-1-i] = temp; } }

编写程序，将若干整数从键盘输入，以单链表形式存储起来，然后计算单链表中结点的个数（其中指针P指向该链表的第一个结点）。

#include <iostream> using namespace std; #define ElemType int #define Status int #define MAXSIZE 100 typedef struct LNode { ElemType data;//数据域 struct LNode* next;//指针域 }LNode, * LinkList; Status InitList(LinkList& L) { L = new LNode; L->next = NULL; return 1; } Status InsertList(LinkList& L, int pos, ElemType e) { LNode* s; LinkList p = L; int j = 0; while (p&&(j<pos-1)) { p = p->next; ++j; } if (!p || j > pos - 1) { return 0; } s = new LNode; s->data = e; s->next = p->next; p->next = s; return 1; } int main() { LinkList P; InitList(P); int num; cout << "请输入整数,按ctrl+z结束输入" << endl; int Length = 1; while (cin>>num) { Length++; InsertList(P, Length, num); } cout <<"单链表结点个数为："<< Length-1 << endl; }

题组三：