【数据结构】09线性表的链式存储实现

定义

线性表的链式存储不需要用连续的存储单元来实现，不需要逻辑上相邻的两个数据元素在物理上也相邻，它是通过链建立其数据元素之间的逻辑关系，因此对线性表的插入、删除不需要移动数据元素，只需要修改连。 为了访问链表，必须找到链表的第一个数据单元，因此实际应用中常用一个称为“表头(Header)”的指针指向链表的第一个单元，并用它表示一个具体的链表。

结点的结构定义 typedef int ElementType; typedef struct LNode* PtrToLNode; typedef PtrToLNode Position; typedef PtrToLNode List; struct LNode { ElementType Data; PtrToLNode Next; }; 相关操作 初始化 List MakeEmpty(List L) { L = (LNode*)malloc(sizeof(LNode)); L->Next = NULL; return L; } 插入

bool Insert(List L, ElementType X, int i) { int cnt = 0; List p = L; //printf("p: %d\n", p->Data); while (p != NULL && cnt != i-1) { p = p->Next; cnt++; } //printf("cnt: %d\n", cnt); if (p == NULL || cnt != i - 1) { printf("insert error!\n"); return false; } else { List temp = (LNode*)malloc(sizeof(LNode) * 1); temp->Data = X; temp->Next = p->Next; p->Next = temp; } return true; } 求表长 int ListLength(List L) { int length = 0; List p = L->Next; while (p != NULL) { p = p->Next; length++; } return length; } 查找 按序号查找 ElementType Findkth(List L, int K) { //找到第i个结点的值 List p = L->Next; int i = 1; while (p != NULL && i != K) { p = p->Next; i++; } if (p == NULL || i != K) { printf("can't find!\n"); return -1; } else { return p->Data; } } 按值查找 Position Find(List L, ElementType X) { //由数值返回其结点位置 List p = L->Next; while (p != NULL && p->Data !=X) { p = p->Next; } if (p->Data == X) { return p; } else{ return NULL; } } 删除 bool Deletei(List L, int i) { //删除第i个结点 List p=L, q = L; int cnt = 0; while (p != NULL && cnt!=i) { cnt++; q = p; p = p->Next; } if (p == NULL || cnt != i) { return false; } q->Next = p->Next; free(p); return true; } 完整代码 # include <stdio.h> # include <stdlib.h> typedef int ElementType; typedef struct LNode* PtrToLNode; typedef PtrToLNode Position; typedef PtrToLNode List; struct LNode { ElementType Data; PtrToLNode Next; }; List MakeEmpty(List L) { L = (LNode*)malloc(sizeof(LNode)); L->Next = NULL; return L; } bool Insert(List L, ElementType X, int i) { int cnt = 0; List p = L; //printf("p: %d\n", p->Data); while (p != NULL && cnt != i-1) { p = p->Next; cnt++; } //printf("cnt: %d\n", cnt); if (p == NULL || cnt != i - 1) { printf("insert error!\n"); return false; } else { List temp = (LNode*)malloc(sizeof(LNode) * 1); temp->Data = X; temp->Next = p->Next; p->Next = temp; } return true; } void print_link(List L) { List p = L->Next; while (p != NULL) { printf("Node : %d\n", p->Data); p = p->Next; } } int ListLength(List L) { int length = 0; List p = L->Next; while (p != NULL) { p = p->Next; length++; } return length; } ElementType Findkth(List L, int K) { //找到第i个结点的值 List p = L->Next; int i = 1; while (p != NULL && i != K) { p = p->Next; i++; } if (p == NULL || i != K) { printf("can't find!\n"); return -1; } else { return p->Data; } } Position Find(List L, ElementType X) { //由数值返回其结点位置 List p = L->Next; while (p != NULL && p->Data !=X) { p = p->Next; } if (p->Data == X) { return p; } else{ return NULL; } } bool Deletei(List L, int i) { //删除第i个结点 List p=L, q = L; int cnt = 0; while (p != NULL && cnt!=i) { cnt++; q = p; p = p->Next; } if (p == NULL || cnt != i) { return false; } q->Next = p->Next; free(p); return true; } int main() { List L = NULL; L = MakeEmpty(L); printf("Finish init!\n"); ElementType X; int N; scanf_s("%d", &N); while (N--) { scanf_s("%d", &X); if (Insert(L, X, 1) == false) { printf("insert error!\n"); } } print_link(L); int length = ListLength(L); printf("the list's length: %d\n", length); /*int x = Findkth(L, 2); printf("find: %d\n", x); List p = Find(L, 5); printf("findp: p->data: %d\n", p->Data);*/ if (bool(Deletei(L, 2))) { printf("Delete Sucessfully!\n"); } print_link(L); length = ListLength(L); printf("the list's length: %d\n", length); }