-
链式存储结构
-
存储方式:用一组任意的存储单元存储线性表中的数据元素,通过每个结点的 指针将数据元素连接在一起
- 单链表:具有一个指针,指向后继元素
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;
Original: https://www.cnblogs.com/RadiumGalaxy/p/16750343.html
Author: RadiumStar
Title: 02 线性表 | 数据结构与算法
原创文章受到原创版权保护。转载请注明出处:https://www.johngo689.com/604162/
转载文章受原作者版权保护。转载请注明原作者出处!