网站程序和数据库,哈尔滨广告制作公司,html5 微网站 源码,医院网站建设合同目录
线性表的定义及其基本操作#xff08;顺序表插入、删除、查找、修改#xff09;
四、线性表的链接存储结构
1. 单链表
2. 循环链表
a. 循环链表节点结构体
b. 创建新节点
c. 在循环链表末尾插入节点
d. 删除循环链表中指定值的节点
e. 在循环链表中查找指定值的…目录
线性表的定义及其基本操作顺序表插入、删除、查找、修改
四、线性表的链接存储结构
1. 单链表
2. 循环链表
a. 循环链表节点结构体
b. 创建新节点
c. 在循环链表末尾插入节点
d. 删除循环链表中指定值的节点
e. 在循环链表中查找指定值的节点
f. 修改循环链表中指定节点的值
g. 打印循环链表
h. 释放循环链表内存空间
i. 主函数
j. 代码整合 线性表的定义及其基本操作顺序表插入、删除、查找、修改
一个线性表是由零个或多个具有相同类型的结点组成的有序集合。 按照线性表结点间的逻辑顺序依次将它们存储于一组地址连续的存储单元中的存储方式被称为线性表的顺序存储方式。按顺序存储方式存储的线性表具有顺序存储结构一般称之为顺序表。换言之在程序中采用定长的一维数组按照顺序存储方式存储的线性表被称为顺序表。 【数据结构】线性表一线性表的定义及其基本操作顺序表插入、删除、查找、修改-CSDN博客https://blog.csdn.net/m0_63834988/article/details/132089038?spm1001.2014.3001.5501
四、线性表的链接存储结构
1. 单链表 顺序表的优点是存取速度快。但是无论是插入一个结点还是删除一个结点都需要调整一批结点的地址。要克服该缺点就必须给出一种不同于顺序存储的存储方式。用链接存储方式存储的线性表被称为链表可以克服上述缺点。 链表中的结点用存储单元若干个连续字节来存放存储单元之间既可以是存储空间上连续的也可以是不连续的甚至可以零散地分布在存储空间中的任何位置。换言之链表中结点的逻辑次序和物理次序之间并无必然联系。最重要的是链表可以在不移动结点位置的前提下根据需要随时添加删除结点动态调整。 【数据结构】线性表二单链表及其基本操作创建、插入、删除、修改、遍历打印-CSDN博客https://blog.csdn.net/m0_63834988/article/details/133914875?spm1001.2014.3001.5501
2. 循环链表 从单链表的一个结点出发只能访问到链接在它后面的结点而无法访问位于它前面的结点这对一些实际应用很不方便。解决的办法是把链接结构“循环化”即把表尾结点的next域存放指向哨位结点的指针而不是存放空指针NULL这样的单链表被称为循环链表。循环链表使用户可以从链表的任何位置开始访问链表中的任意结点。 a. 循环链表节点结构体
typedef struct Node {int data; // 数据域struct Node *next; // 指针域
} Node; 包含一个整型数据域 data 和一个指向下一个节点的指针域 next。
b. 创建新节点
Node* createNode(int data) {Node* newNode (Node*)malloc(sizeof(Node));newNode-data data;newNode-next NULL;return newNode;
}
创建一个新的节点并返回指向该节点的指针 使用 malloc 分配了节点的内存空间将传入的数据赋值给节点的 data 字段并将 next 字段设置为 NULL。
c. 在循环链表末尾插入节点
void insert(Node** head, int data) {Node* newNode createNode(data);if (*head NULL) {*head newNode;(*head)-next *head; // 将尾节点指向头节点形成循环} else {Node* temp *head;while (temp-next ! *head) {temp temp-next;}temp-next newNode;newNode-next *head;}
}
调用 createNode 函数创建一个新节点并将新节点的指针保存在 newNode 中。检查链表是否为空 如果为空则将 head 指向新节点并将新节点的指针域 next 设置为指向自己这样形成一个只有一个节点的循环链表。 如果链表不为空遍历链表找到尾节点将尾节点的指针域 next 指向新节点新节点的指针域 next 指向头节点完成节点的插入操作。 d. 删除循环链表中指定值的节点
void deleteNode(Node** head, int data) {if (*head NULL) {return;}Node* currNode *head;Node* prevNode NULL;while (currNode-next ! *head) {if (currNode-data data) {if (prevNode NULL) {Node* lastNode *head;while (lastNode-next ! *head) {lastNode lastNode-next;}*head currNode-next;lastNode-next *head;} else {prevNode-next currNode-next;}free(currNode);return;}prevNode currNode;currNode currNode-next;}if (currNode-data data) {if (prevNode NULL) {*head NULL;} else {prevNode-next *head;}free(currNode);}
}
检查链表是否为空如果为空则直接返回。定义两个指针 currNode 和 prevNode currNode 指向当前节点初始时指向头节点prevNode指向前一个节点初始为 NULL遍历链表如果找到了与指定值相等的节点则判断该节点是否为头节点 如果是头节点则需要找到尾节点将其指向新的头节点并更新 *head 的值为删除节点的下一个节点最后释放删除节点的内存。如果不是头节点直接将前一个节点的指针域 next 指向删除节点的下一个节点然后释放删除节点的内存。
e. 在循环链表中查找指定值的节点
Node* search(Node* head, int data) {if (head NULL) {return NULL;}Node* currNode head;while (currNode-next ! head) {if (currNode-data data) {return currNode;}currNode currNode-next;}if (currNode-data data) {return currNode;}return NULL;
}链表是否为空如果为空则返回 NULL。定义一个指针 currNode初始时指向头节点。遍历链表如果找到了与指定值相等的节点则返回该节点的指针。如果遍历完整个链表都没找到相等的节点则返回 NULL。 f. 修改循环链表中指定节点的值
void modify(Node* head, int oldData, int newData) {Node* nodeToModify search(head, oldData);if (nodeToModify ! NULL) {nodeToModify-data newData;}
}
调用上述e中 search 函数查找指定值的节点并将返回的节点指针保存在 nodeToModify 中如果找到了节点则将该节点的数据域 data 更新为 newData。
g. 打印循环链表
void printList(Node* head) {if (head NULL) {printf(循环链表为空\n);return;}Node* currNode head;do {printf(%d , currNode-data);currNode currNode-next;} while (currNode ! head);printf(\n);
}
检查链表是否为空如果为空则打印提示信息并返回。定义一个指针 currNode初始时指向头节点。使用 do-while 循环遍历链表打印当前节点的数据然后将指针移动到下一个节点直到回到头节点为止。
h. 释放循环链表内存空间
void freeList(Node** head) {if (*head NULL) {return;}Node* currNode *head;Node* nextNode NULL;while (currNode-next ! *head) {nextNode currNode-next;free(currNode);currNode nextNode;}free(currNode);*head NULL;
}
检查链表是否为空如果为空则直接返回。定义两个指针 currNode 和 nextNode currNode 指向当前节点初始时指向头节点nextNode指向下一个节点初始为 NULL使用 while 循环遍历链表将 nextNode 指向 currNode 的下一个节点释放 currNode 指向的节点的内存然后将 currNode 更新为 nextNode。重复以上步骤直到遍历完整个链表并最后释放头节点的内存。
i. 主函数
int main() {Node* head NULL;// 在循环链表中插入节点insert(head, 10);insert(head, 20);insert(head, 30);insert(head, 40);// 打印循环链表printf(循环链表: );printList(head);// 删除循环链表中的节点deleteNode(head, 20);// 打印删除节点后的循环链表printf(删除节点后的循环链表: );printList(head);// 在循环链表中查找节点Node* searchResult search(head, 30);if (searchResult ! NULL) {printf(找到节点 %d\n, searchResult-data);} else {printf(未找到节点\n);}// 修改循环链表中的节点值modify(head, 30, 50);// 打印修改节点值后的循环链表printf(修改节点值后的循环链表: );printList(head);// 释放循环链表内存空间freeList(head);return 0;
}
定义一个指向头节点的指针 head初始时为 NULL。通过调用 insert 函数在循环链表中插入了四个节点其数据分别为 10、20、30 和 40。调用 deleteNode 函数删除了值为 20 的节点并再次调用 printList 函数打印删除节点后的循环链表。调用 search 函数查找值为 30 的节点并根据返回结果打印相应的信息。调用 modify 函数修改值为 30 的节点的数据为 50最后调用 freeList 函数释放循环链表占用的内存空间。 j. 代码整合
#include stdio.h
#include stdlib.h// 定义循环链表节点结构体
typedef struct Node {int data; // 数据域struct Node *next; // 指针域
} Node;// 创建新节点
Node* createNode(int data) {Node* newNode (Node*)malloc(sizeof(Node));newNode-data data;newNode-next NULL;return newNode;
}// 在循环链表末尾插入节点
void insert(Node** head, int data) {Node* newNode createNode(data);if (*head NULL) {*head newNode;(*head)-next *head; // 将尾节点指向头节点形成循环} else {Node* temp *head;while (temp-next ! *head) {temp temp-next;}temp-next newNode;newNode-next *head;}
}// 删除循环链表中指定值的节点
void deleteNode(Node** head, int data) {if (*head NULL) {return;}Node* currNode *head;Node* prevNode NULL;while (currNode-next ! *head) {if (currNode-data data) {if (prevNode NULL) {Node* lastNode *head;while (lastNode-next ! *head) {lastNode lastNode-next;}*head currNode-next;lastNode-next *head;} else {prevNode-next currNode-next;}free(currNode);return;}prevNode currNode;currNode currNode-next;}if (currNode-data data) {if (prevNode NULL) {*head NULL;} else {prevNode-next *head;}free(currNode);}
}// 在循环链表中查找指定值的节点
Node* search(Node* head, int data) {if (head NULL) {return NULL;}Node* currNode head;while (currNode-next ! head) {if (currNode-data data) {return currNode;}currNode currNode-next;}if (currNode-data data) {return currNode;}return NULL;
}// 修改循环链表中指定节点的值
void modify(Node* head, int oldData, int newData) {Node* nodeToModify search(head, oldData);if (nodeToModify ! NULL) {nodeToModify-data newData;}
}// 打印循环链表
void printList(Node* head) {if (head NULL) {printf(循环链表为空\n);return;}Node* currNode head;do {printf(%d , currNode-data);currNode currNode-next;} while (currNode ! head);printf(\n);
}// 释放循环链表内存空间
void freeList(Node** head) {if (*head NULL) {return;}Node* currNode *head;Node* nextNode NULL;while (currNode-next ! *head) {nextNode currNode-next;free(currNode);currNode nextNode;}free(currNode);*head NULL;
}int main() {Node* head NULL;// 在循环链表中插入节点insert(head, 10);insert(head, 20);insert(head, 30);insert(head, 40);// 打印循环链表printf(循环链表: );printList(head);// 删除循环链表中的节点deleteNode(head, 20);// 打印删除节点后的循环链表printf(删除节点后的循环链表: );printList(head);// 在循环链表中查找节点Node* searchResult search(head, 30);if (searchResult ! NULL) {printf(找到节点 %d\n, searchResult-data);} else {printf(未找到节点\n);}// 修改循环链表中的节点值modify(head, 30, 50);// 打印修改节点值后的循环链表printf(修改节点值后的循环链表: );printList(head);// 释放循环链表内存空间freeList(head);return 0;
}
