线性表的链式表示与实现
时间: 2023-10-21 13:05:45 浏览: 45
线性表是一种常用的数据结构,它是由一系列具有相同数据类型的元素组成的有限序列。线性表的链式表示是一种基于指针的表示方法,它通过指针将线性表中的元素连接起来。
链式表示的实现通常有两种方式:单链表和双向链表。
1. 单链表
单链表是一种最简单的链式表示方式,它由一系列节点组成,每个节点包含两部分数据:数据域和指针域。其中,数据域存储节点的数据,指针域存储下一个节点的地址。
单链表的实现需要定义一个节点结构体,在结构体中定义数据域和指针域。我们可以使用指针变量来表示链表的头节点,通过遍历指针域来访问链表中的各个节点。
定义节点结构体:
```c
typedef struct ListNode{
int data;
struct ListNode *next;
}ListNode;
```
创建单链表:
```c
ListNode* createList(int a[], int n){
ListNode* head = (ListNode*)malloc(sizeof(ListNode));
ListNode* p = head;
for(int i = 0; i < n; i++){
ListNode* node = (ListNode*)malloc(sizeof(ListNode));
node->data = a[i];
node->next = NULL;
p->next = node;
p = node;
}
return head;
}
```
其中,a[] 是存储数据的数组,n 是数组长度。
遍历单链表:
```c
void traverseList(ListNode* head){
ListNode* p = head->next;
while(p){
printf("%d ", p->data);
p = p->next;
}
printf("\n");
}
```
2. 双向链表
双向链表是在单链表的基础上增加了一个指向前驱节点的指针域,它可以实现双向遍历,但是相对于单链表,它需要额外的空间开销。
定义节点结构体:
```c
typedef struct DoubleListNode{
int data;
struct DoubleListNode *prev;
struct DoubleListNode *next;
}DoubleListNode;
```
创建双向链表:
```c
DoubleListNode* createList(int a[], int n){
DoubleListNode* head = (DoubleListNode*)malloc(sizeof(DoubleListNode));
DoubleListNode* p = head;
for(int i = 0; i < n; i++){
DoubleListNode* node = (DoubleListNode*)malloc(sizeof(DoubleListNode));
node->data = a[i];
node->prev = p;
node->next = NULL;
p->next = node;
p = node;
}
return head;
}
```
遍历双向链表:
```c
void traverseList(DoubleListNode* head){
DoubleListNode* p = head->next;
while(p){
printf("%d ", p->data);
p = p->next;
}
printf("\n");
}
```