[数据结构]基本概念、单链表操作
最后更新于：2022-04-01 15:56:15
###1.数据在内存中的存储方式
数据在计算机程序中都是存储在内存空间中的.
1. 连续内存空间，比如申请一个数组，申请内存的大小事先知道。【数组】
1. 非连续内存空间，特点是申请次数无限制，每次固定大小。【链表】
###2.时间复杂度和空间复杂度
- 时间复杂度：同一问题可用不同的算法解决，一个算法的质量优劣将影响算法乃至程序的效率。算法的时间复杂度是一个函数，定量描述算法的运行时间，通常用O表示.
- 空间复杂度：一个算法在运行过程中占用存储空间大小的度量，包括算法本身所占的存储空间、数据输出数据所占用的存储空间的大学、运行过程中临时占用的存储空间的大小这三个方面。
###3.衡量一个算法的优劣的标准
- **正确性**.
所写算法能满足具体问题的要求，对于任何合法的输入可以得出正确的结果。
- **可读性.**
晦涩难懂的算法不易于交流、推广、修改、拓展、维护，在写算法的时候，要尽量写的简明易懂。
- **健壮性.**
输入数据非法时，算法也会做出相应的判断，不会因为输入的错误造成程序瘫痪。
- **时间复杂度和空间复杂度.**
理想的算法应该是时间复杂度和空间复杂度都最佳。对于一个算法，时间复杂度和空间复杂度往往相互影响。
###4.链表基本操作
##### 4.1链表结构体定义
~~~
#include <stdio.h>
#include <stdlib.h>
#include <MATH.h>
typedef struct linklist
{
int data;
struct linklist *next; //单链表
}linknode,*linklistp;
~~~
##### 4.2.头部插入新节点
~~~
//返回头部
linklistp insert_head(linklistp head,linklistp newnode){
newnode->next=head;
head=newnode;
return head;
}
~~~
##### 4.3. 尾部插入新节点
~~~
linklistp insert_tail(linklistp head,linklistp newnode){
if(head==NULL){
head=newnode;
}else{
linklistp temp=head;
while(temp->next!=NULL){
temp=temp->next;
}
newnode->next=temp->next;
temp->next=newnode;
}
return head;
}
~~~
##### 4.4 删除子节点
~~~
//删除节点
linklistp list_delete(linklistp head,int a){
linklistp temp=head;
//1.temp为空，返回NULL
if(temp==NULL){
printf("链表为空\n");
return NULL;
}
//2.正好是首节点
if(temp->data==a){
head=head->next;
free(temp);
return head;
}
//3.不在首节点
linklistp prev=head;
temp=head->next;
while(temp!=NULL&&temp->data!=a){
prev=temp;
temp=temp->next;
}
//3.1 没找到
if(temp==NULL){
printf("不存在\n");
return NULL;
}
prev->next=temp->next;
return head;
}
~~~
##### 4.5查找节点
~~~
//查找第i个元素
int getElem(linklistp head,int i,int a){
if (head->next==NULL)
{
printf("link list is NULL");
return 0;
}
linklistp temp=head;
int j=0;
while(temp->next&&j<i){
temp=temp->next;
++j;
}
if(!temp||j>i){
printf(" 不存在第i个元素\n");
}
a=temp->data;
return a;
}
~~~
##### 4.6 判断链表是否为空
~~~
//判断链表是否为空
_Bool isEmpty(linklistp head){
if (head->next==NULL)
{
printf("链表为空\n");
return 1;
}
return 0;
}
~~~
#####4.7遍历链表
~~~
void output(linklistp head){
linklistp temp=head;
while(temp){
printf("%d\t", temp->data);
temp=temp->next;
}
printf("\n");
}
~~~
##### 4.8 测试代码
~~~
int main(){
linklistp head=NULL;
for (int i = 0; i < 10; ++i)
{
/* code */
linklistp newnode=(linklistp)malloc(sizeof(linknode));
newnode->data=i*10+2;
newnode->next=NULL;
head=insert_head(head,newnode);
}
output(head);
printf("*********删除节点*******\n");
int data=0;
printf("请输入要删除的数据：\n");
scanf("%d",&data);
linklistp temp=list_delete(head,data);
if (temp==NULL)
{
printf("def failture or not has this node");
}else{
head=temp;
output(head);
}
printf("**************************\n");
printf("enter the num you want to find:\n");
printf("%d\n",getElem(head,2,data));
return 0;
}
~~~
