标签：02 Node head return 线性表 int 元素 next 数据结构

1. 线性表

线性表的定义
1. 特点：
  1. 存在唯一一个被称为第一个的数据元素
  2. 存在唯一一个被称为最后一个的数据元素
  3. 除了第一个元素之外，其他的数据元素都有唯一一个直接前驱
  4. 除了最后一个元素之外，其他的数据元素都有唯一一个直接后驱
2. 定义：是由 \(n(n\ge 0)\) 个相同的数据元素组成的有限序列
3. 逻辑特征
  1. 有限性：数据元素的个数是有限的
  2. 相同性：数据元素的元素类型是相同的
  3. 相继性（线性性）：\(a_1\) 为表中的第一个元素，无前驱元素，\(a_n\) 为表中最后一个元素，无后驱元素；对于 \(1<i<n\) ， \(a_{i-1}\) 为 \(a_{i}\) 的直接前驱， \(a_{i+1}\) 为 \(a_{i}\) 的直接后驱
4. 基本操作 \(Operations\)
  1. 求线性表的长度 Lenlist(L)
  2. 获取线性表中的元素 GetElem(L , i)
  3. 通过值来查找线性表当中的元素 SearchElem(L , Val)
  4. 插入元素 InsertElem(L , i , Elem)
  5. 删除元素 DeleteElem(L , i)

线性表的存储结构设计

连续存储结构(数组)

存储方式：依次将元素存放进连续的存储空间中
顺序表示： \(loc(a_i) = loc(a_1)+(i-1)*c\)
存储特点：逻辑上相邻的元素，物理结构上也相邻
\(Operations\)

// 1. 插入元素 O(n)
int insertElem(list *L , Datatype x , int i){
    if((*L).last >= maxsize - 1){   //overflow
        printf("Overflow\n");
        return -1;
    }
    else if(i < 1 || i > (*L).last + 1){    //wrong location
        printf("Error\n");
        return -1;
    }
    else{
        for(int j = (*L).last ; j >= i ; --j){  //move the elements
            (*L).data[j + 1] = (*L).data[j];
        }
        (*L).data[i] = x;
        (*L).last++;
    }
    return 1;
}

// 2. 删除元素 O(n)
int deleteElem(list *L , int i){
    if(i < 1 || i > (*L).last + 1){    //wrong location
        printf("Error\n");
        return -1;
    }
    else {
        for(int j = i ; j <= (*L).last ; ++j){
            (*L).data[j - 1] = (*L).data[j];
        }
        (*L).last--;
    }
}

// 3. 按值查找 O(n)
int searchElem(list *L , Datatype x){
    int i = 1;
    while(i <= (*L).last && x != (*L).data[i - 1]){
        ++i;
    }
    if(i <= (*L).last) return i - 1;
    return -1;  //can not find
}

// 4. 按位置查找 O(1)
int getElem(list *L , int i){
    if(i < 1 || i > (*L).last + 1){    //wrong location
        printf("Error\n");
        return -1;
    }
    return (*L).data[i - 1]
}

连续存储的优缺点
1. 优点
  1. 顺序表的存储结构简单
  2. 随机存储，按位置取值速度快
  3. 存储效率高，无需增加逻辑关系的占用空间
2. 缺点
  1. 删除插入速度慢
  2. 预先分配内存大

\(\quad\)
\(存储效率 = \frac{数据元素占用空间}{数据元素占用空间+逻辑关系占用空间}\)
\(\quad\)

链式存储结构

存储方式：用一组任意的存储单元存储线性表中的数据元素，通过每个结点的指针将数据元素连接在一起
单链表：具有一个指针，指向后继元素

typedef struct Node{
    datatype data;
    struct Node *next;
}Node , *head;

\(Operations\)

// 1. 建立单链表
void createList(){
    Node head = new Node();
    head->next = NULL;
}

// 2. 插入元素
int insertList(Node &L , int i , datatype x){
    Node *p = head;
    int j = 0;
    while(p && j < i - 1){
        p = p->next;
        j++;
    }
    if(!p) return -1;
    Node *temp = new Node;
    temp->data = x;     // insert
    temp->next = p->next;
    p->next = temp;
    return 1;
}

// 3. 删除元素
int deleteList(Node &L , int i){
    Node *p = head;
    int j = 0;
    while((p->next) && j < i - 1){
        p = p->next;
        j++;
    }
    if(!(p->next)) return -1;
    Node *temp = p->next;
    p->next = temp->next;
    delete temp;
    return 1;
}

// 4. 通过位置查找元素
datatype getList(Node &L , int i){
    Node *p = head;
    int j = 0;
    while(p && j < i - 1){
        p = p->next;
        j++;
    }
    if(!p) return -1;
    return p->data;
}

// 5. 通过值来查找元素
int searchList(Node &L , datatype x){
    Node *p = head;
    int j = 0;
    while(p && p->data != x){
        p = p->next;
        ++j;
    }
    if(!p) {
        printf("Not Find!");
        return -1;
    }
    return j;
}

双链表：前驱指针 *prev 和后继指针 *next
\(Operations\) 要处理两个指针

// 1. 初始化
typedef struct DulNode{
    datatype data;
    struct DulNode *prev , *next;
}DulNode , *head;

// 2. 插入元素(先右后左)
s->data = _data;
s->next = p->next;
p->next->prev = s;
p->next = s;
s->prev = p;

// 3. 删除元素
p->prev->next = p->next;
p->next->prev = p->prev;
delete p;

连续设计和连接设计的对比

Parameters	连续设计	链接设计
表的容量	固定，不易扩充	灵活，易扩充
存取操作	随机访问存取，速度快	顺序访问存取，速度慢
时间	插入、删除操作费时间	访问元素费时间
空间	估算长度，浪费空间	实际长度

链接存储设计的数组实现

data	next
data1	1
	2
\(\cdots\)	\(\cdots\)
	max_size - 1
	-1

结点：

#define max_size 1024    \\数组最大容量
typedef int datatype;
typedef int cursor;
typedef struct{
 datatype data;
 cursor next;
}node;

node nodepool[max_size];     // 存储池（数组）
cursor avail;    // 空闲空间的位置

初始化

for(int i=0; i < max_size - 1; i++){
     nodepool[i].next = i + 1;
}
nodepool[max_size - 1].next = -1;
avail = 0;   //avail 初始化

结点 node 的分配

cursor getNode(){
     cursor p;
     if(avail == -1) p = -1;
     else {
         p = avail;
         avail = nodepool[avail].next;
     }
     return p;
 }

结点 node 的回收

void freeNode(cursor p){
     nodepool[p].next = avail;
     avail = p;
}

静态链表查找算法

cursor findNode(cursor L , int i){
     cursor p = L;
     int j = 0;
     while(nodepool[p].next != -1 && (j < i>)){
         p = nodepool[p].next;
         ++j;
     }
     if(i == j) return p;
     else return -1;
}

2. \(Applications\)

合并有向链表

ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
	ListNode* preHead = new ListNode(-1);

	ListNode* prev = preHead;
	while (l1 != nullptr && l2 != nullptr) {
		if (l1->val < l2->val) {
			prev->next = l1;
			l1 = l1->next;
		} 
		else {
			prev->next = l2;
			l2 = l2->next;
		}
		prev = prev->next;
	}

	prev->next = (l1 == nullptr) ? l2 : l1;// 合并剩余链表
	return preHead->next;
}

反转链表

就地反转

graph LR A(head)-.->B(nextp) B-->C(cur) C--> D(p) D-.->E(NULL)

反转箭头为：

graph LR A(head)-.->B(nextp) B-.->C(cur) C==>B C--> D(p) D-.->E(NULL)

``` cpp
 ListNode* reverseList(ListNode* head) {
 	if(head == nullptr) return head;
 	ListNode* nextp = nullptr;
 	ListNode* cur = head;
 	ListNode* p = head -> next;
 	while(p){
 		cur -> next = nextp;
 		nextp = cur;
 		cur = p;
 		p = cur -> next;
 	}
 	cur -> next = nextp;
 	return cur;
 }
```

递归：处理好 k之后，将 k-1 的箭头倒转；

graph LR A(1)-->B(2) B-.-C(k -1) C-.-> D(k) D==>C E(k+1)-->D F(n)-.->E

ListNode* reverseList(ListNode* head) {
    if(!head || !(head -> next)) return head;
    ListNode* new_Head =  reverseList(head -> next);
    head -> next -> next = head;
    head -> next = nullptr;
    return new_Head;
}

标签：02,Node,head,return,线性表,int,元素,next,数据结构
From： https://www.cnblogs.com/RadiumGalaxy/p/16750343.html

02 线性表 | 数据结构与算法

1. 线性表

2. \(Applications\)

相关文章

赞助商

阅读排行