文章目录
线性表的链式存储结构（单链表）
这里是数据结构个人学习的笔记记录，如有问题欢迎指正说明
单链表的定义
n个结点链结成一个链表。每个结点由数据域和指针域两部分组成，在此处我们之研究结点只含一个指针域的链表，即单链表。
结点的表示方法：
typedef struct LinkNode
{
char data;
struct LinkNode *next;
}LNode,*LinkList,*NodePtr;
我们把链表中的第一个结点的存储位置叫做头指针，整个链表的存取必须从头指针开始。为了方便操作，我们还可以在单链表的第一个结点前附设一个结点，称为头结点。注意头结点不是必不可少的。头结点和头指针的异同如下图：
单链表的相关操作实现
初始化
/* 初始化 */
LinkList initLinkList(){
NodePtr tempHeader=(NodePtr)malloc(sizeof(LNode));
tempHeader->data='\0';
tempHeader->next=NULL;
return tempHeader;
}
依次对单链表中的每个数据元素输出
/* 依次对L的每个数据元素输出 */
Status ListTraverse(LinkList L)
{
LinkList p=L->next;
while(p)
{
visit(p->data);//vist函数为输出值
p=p->next;
}
printf("\n");
return OK;
}
在单链表中指定位置之前插入新的数据元素
/* 在单链表中指定位置之前插入新的数据元素 */
void insertElement(NodePtr paraHeader,char paraChar,int paraPosition){
NodePtr p,q;
p=paraHeader;
for(int i=0;i<paraPosition;i++){
p=p->next;
if(p==NULL){
printf("The postion %d is beyond the scope of the list.",paraPosition);
return;
}
}
q=(NodePtr)malloc(sizeof(LNode));
q->data=paraChar;
printf("linking\r\n");
q->next=p->next;
p->next=q;
}
删除线性表中指定的数据元素
/* 删除线性表的指定位置的数据元素 */
void deleteElement(NodePtr paraHeader,char paraChar){
NodePtr p,q;
p=paraHeader;
while((p->next!=NULL)&&(p->next->data!=paraChar)){
p=p->next;
}
if(p->next==NULL){
printf("Cannot delete %c\r\n",paraChar);
return;
}
q=p->next;
p->next=q->next;
free(q);
}
尾插的实现
void appendElement(NodePtr paraHeader, char paraChar){
NodePtr p, q;
// Step 1. Construct a new node.
q = (NodePtr)malloc(sizeof(LNode));
q->data = paraChar;
q->next = NULL;
// Step 2. Search to the tail.
p = paraHeader;
while (p->next != NULL) {
p = p->next;
}// Of while
// Step 3. Now add/link.
p->next = q;
}
新增操作
返回单链表中元素的个数
/* 返回单链表中数据元素个数 */
int ListLength(NodePtr paraHeader)
{
int i=0;
NodePtr paraNew=paraHeader->next;
while(paraNew)
{
i++;
paraNew=paraNew->next;
}
return i;
}
头插的实现
/* 随机产生n个元素的值，建立带表头结点的单链线性表L（头插法） */
void CreateListHead(LinkList *L,int n)
{
LinkList p;
int i;
srand(time(0));
*L=(LinkList)malloc(sizeof(Node));
(*L)->next=NULL;
for(i=0;i<n;i++)
{
p=(LinkList)malloc(sizeof(Node));
p->data=rand()%100+1;
p->next=(*L)->next;
(*L)->next=p;
}
}
返回指定位序的值
/* 返回线性表中第i个数据元素的值 */
char GetElement(NodePtr paraHeader,int i)
{
int j=1;
NodePtr p;
p=paraHeader->next;
while(p&&j<i)
{
p=p->next;
++j;
}
if(!p||j>i)
{
printf("Invalid number!\n");
return -1;
}
return p->data;
}
返回第一个满足指定数据元素的位序
/* 返回单链表中第1个与paraChar满足关系的数据元素的位序。 */
/* 若这样的数据元素不存在，则返回值为-1 */
char LocateElement(NodePtr paraHeader,char paraChar)
{
int i=0;
NodePtr p=paraHeader->next;
while(p)
{
i++;
if(p->data==paraChar)
return i;
p=p->next;
}
return -1;
}
整表删除
/* 初始条件：链式线性表L已存在。操作结果：将L重置为空表 */
Status ClearList(LinkList *L)
{
LinkList p,q;
p=(*L)->next;
while(p)
{
q=p->next;
free(p);
p=q;
}
(*L)->next=NULL;
return OK;
}
链式存储的代码实现
#include<stdio.h>
#include<malloc.h>
typedef struct LinkNode{
char data;
struct LinkNode *next;
}LNode,*LinkList,*NodePtr;
LinkList initLinkList(){
NodePtr tempHeader=(NodePtr)malloc(sizeof(LNode));
tempHeader->data='\0';
tempHeader->next=NULL;
return tempHeader;
}
void printList(NodePtr paraHeader){
NodePtr p=paraHeader->next;
while(p!=NULL){
printf("%c",p->data);
p=p->next;
}
printf("\r\n");
}
void insertElement(NodePtr paraHeader,char paraChar,int paraPosition){
NodePtr p,q;
p=paraHeader;
for(int i=0;i<paraPosition;i++){
p=p->next;
if(p==NULL){
printf("The postion %d is beyond the scope of the list.",paraPosition);
return;
}
}
q=(NodePtr)malloc(sizeof(LNode));
q->data=paraChar;
printf("linking\r\n");
q->next=p->next;
p->next=q;
}
void deleteElement(NodePtr paraHeader,char paraChar){
NodePtr p,q;
p=paraHeader;
while((p->next!=NULL)&&(p->next->data!=paraChar)){
p=p->next;
}
if(p->next==NULL){
printf("Cannot delete %c\r\n",paraChar);
return;
}
q=p->next;
p->next=q->next;
free(q);
}
/*尾插*/
void appendElement(NodePtr paraHeader, char paraChar){
NodePtr p, q;
// Step 1. Construct a new node.
q = (NodePtr)malloc(sizeof(LNode));
q->data = paraChar;
q->next = NULL;
// Step 2. Search to the tail.
p = paraHeader;
while (p->next != NULL) {
p = p->next;
}// Of while
// Step 3. Now add/link.
p->next = q;
}
/*头插*/
void headElement(NodePtr paraHeader,char paraChar){
NodePtr p,q;
p=paraHeader;
q=(NodePtr)malloc(sizeof(LNode));
q->data=paraChar;
q->next=p->next;
p->next=q;
}
/* 返回线性表中第i个数据元素的值 */
char GetElement(NodePtr paraHeader,int i)
{
int j=1;
NodePtr p;
p=paraHeader->next;
while(p&&j<i)
{
p=p->next;
++j;
}
if(!p||j>i)
{
printf("Invalid number!\n");
return -1;
}
return p->data;
}
/* 返回单链表中第1个与paraChar满足关系的数据元素的位序。 */
/* 若这样的数据元素不存在，则返回值为-1 */
char LocateElement(NodePtr paraHeader,char paraChar)
{
int i=0;
NodePtr p=paraHeader->next;
while(p)
{
i++;
if(p->data==paraChar)
return i;
p=p->next;
}
return -1;
}
/* 初始条件：链式线性表L已存在。操作结果：返回L中数据元素个数 */
int ListLength(NodePtr paraHeader)
{
int i=0;
NodePtr paraNew=paraHeader->next;
while(paraNew)
{
i++;
paraNew=paraNew->next;
}
return i;
}
/* 初始条件：链式线性表L已存在。操作结果：将L重置为空表 */
void ClearList(NodePtr paraHeader)
{
NodePtr p,q;
p=paraHeader->next;
while(p)
{
q=p->next;
free(p);
p=q;
}
paraHeader->next=NULL;
}
void appendInsertDeleteTest(){
// Step 1. Initialize an empty list.
LinkList tempList = initLinkList();
printList(tempList);
// Step 2. Add some characters.
appendElement(tempList, 'H');
appendElement(tempList, 'e');
appendElement(tempList, 'l');
appendElement(tempList, 'l');
appendElement(tempList, 'o');
appendElement(tempList, '!');
headElement(tempList,'w');
printList(tempList);
printf("The sixth element is %c\n",GetElement(tempList,6));
printf("'e' is the %d of the list\n",LocateElement(tempList,'e'));
printf("Length of the list is %d\n",ListLength(tempList));
// Step 3. Delete some characters (the first occurrence).
deleteElement(tempList, 'e');
deleteElement(tempList, 'a');
deleteElement(tempList, 'o');
printList(tempList);
// Step 4. Insert to a given position.
insertElement(tempList, 'o', 1);
printList(tempList);
ClearList(tempList);
printf("Length of the list is %d\n",ListLength(tempList));
}// Of appendInsertDeleteTest
void basicAddressTest(){
LNode tempNode1, tempNode2;
tempNode1.data = 4;
tempNode1.next = NULL;
tempNode2.data = 6;
tempNode2.next = NULL;
printf("The first node: %d, %d, %d\r\n",
&tempNode1, &tempNode1.data, &tempNode1.next);
printf("The second node: %d, %d, %d\r\n",
&tempNode2, &tempNode2.data, &tempNode2.next);
tempNode1.next = &tempNode2;
}
int main(){
appendInsertDeleteTest();
basicAddressTest();
}
样例测试输出
wHello!
The sixth element is o
'e' is the 3 of the list
Length of the list is 7
Cannot delete a
wHll!
linking
woHll!
Length of the list is 0
The first node: 6421984, 6421984, 6421992
The second node: 6421968, 6421968, 6421976
链式存储的优缺点
优点：存储空间可自由扩充
插入、删除等操作不必移动数据，修改效率较高
缺点：读写效率不高，必须采用顺序读取
写在最后
通过对单链表结构和顺序存储结构不同功能时间复杂度的分析，可以得出以下结论：
1，若线性表需要频繁查找，很少进行插入和删除操作时，宜采用顺序存储结构。
2.当线性表中元素个数未知时，宜采用链式存储结构。
噢对了，欢迎移步我另一篇实现方法（手动狗头）
https://blog.csdn.net/AHuRui/article/details/124453661?utm_source=app&app_version=5.3.1
