数据结构基础——内存中数据存储的基本方式（单链表）
一、首先介绍一下数据在内存中的存储(针对于c/c++)：
1、栈区[stack]：由编译器自动分配释放，存放函数的参数值，局部变量的值等。其操作方式类似于数据结构中的栈。
2、堆区[heap]：一般由程序员分配释放，若程序员不释放，程序结束时可能由OS回收。注意它与数据结构中的堆是两回事，分配方式类似于链表（malloc相关的/new）。
3、全局区[静态区]：全局变量和静态变量的存储是放在一块的，初始化的全局变量和静态变量在一块区域，未初始化的全局变量和未初始化的静态变量在相邻的另一块区域。程序结束后由系统释放。
4、文字常量区：存放常量字符串。程序结束后由系统释放。
5、程序代码区：存放函数体的二进制代码。
6、寄存器区：用来保存栈顶指针和指令指针(汇编操作)
二、计算机内存中的两种数据存储的基本方式：数组和链表。
第一种是我们熟知的数组，申请连续内存的空间。
（1）栈空间内申请：int a[100];
（2）堆空间内申请：int *p=malloc(100 *sizeof(int));
如果要查找某个数需要从进行0-99的遍历，如果要插入或删除某个成员需要将后面的成员 移动。所以利用数组可以快速的查表，而不利用数组进行修改。
第二种是链表，申请分散的内存空间，每次固定大小，通过指针连接起来，我们主要看看单链表。
单链表：一个节点由数据（图上的0x100等）和next指针构成，head为头指针，指向第一个结点的地址。每个节点的next指针指向下一个结点地址。
其实每个结点就是一个结构体。
typedef struct LinkList
{
int data; //数据可以为char，struct，*，等等类型
struct LinkList *next; //指向下一个结点的地址
}Linknode,*linklistp;
//定义结构体为Linknode，linklistp为结构体指向Linknode这个结构体的指针。
//在主函数内定义头指针为空
linklistp head=NULL;
1.单链表的插入操作 分为三种，第一种头插，第二种中间插入，第三种尾插。
（1）头插法
思路：首先让插入结点的next指针指向原来结点（图中1），然后让head（头指针）指向插入结点（图中2）。红线为断了的指针。
关键代码：
linklistp insert_head(linklistp head,linklistp newnode)
{
//debug版本有，判断newnode是否为空
assert(newnode);
newnode->next=head;
head=newnode;
return head;
}
这里的系统assert()函数（按住command点击函数）我们看看 assert宏的原型定义在中，其作用是如果它的条件返回错误，则终止程序执行。
// assert.h中定义
#if __DARWIN_UNIX03
#define assert(e) \
(__builtin_expect(!(e), 0) ? __assert_rtn(__func__, __FILE__, __LINE__, #e) : (void)0)
#else // !__DARWIN_UNIX03
#define assert(e) \
(__builtin_expect(!(e), 0) ? __assert (#e, __FILE__, __LINE__) : (void)0)
void __assert_rtn(const char *, const char *, int, const char *) __dead2
我们再看看__dead2里面是什么？一个宏定义。
//cdefs.h
#define __dead2 __attribute__((noreturn))
（2）尾插法
思路：首先让插入结点的next指向NULL，然后让最后结点的next指向插入结点。
关键代码：
linklistp insert_tail(linklistp head,linklistp newnode)
{
assert(newnode);
if(head==NULL)
{
head=newnode;
}
else
{
linklistp temp=head;
while (temp->next != NULL)
temp=temp->next;
newnode->next=NULL;
temp->next=newnode;
}
return head;
}
（3）查找数据并在后面插入
思路：首先定义一个遍历链表的指针，然后查找要找的数据所在的结点，然后让插入结点的next指向数据所在结点的next结点，最后让数据所在结点的next指向插入结点。千万不要忘了释放不需要的指针。
关键代码：
linklistp insert_local(linklistp head,int data,linklistp newnode)
{
linklistp temp=head; //遍历指针
if(temp==NULL)
{
return NULL;
}
while (temp != NULL && temp->data !=data) {
temp=temp->next;
}
if(temp ==NULL)
return NULL;
newnode->next=temp->next;
temp->next = newnode;
free(temp); //释放不需要的指针
return head;
}
由于查询操作已经在插入的（3）中讲了这里就不再讲了。
2.单链表删除操作（ 删除查询的结点）
思路：首先需要一个记录结点的指针和一个遍历指针，然后查找要找的数据所在的结点，并记录了前一个结点，让前一个结点的next指向查找到结点的next指向的结点。
关键代码：
linklistp delnode(linklistp head,int data)
{
linklistp temp=head; //遍历指针
if(temp==NULL) //链表为空
{
return NULL;
}
if(temp->data == data) //删除结点为第一个结点
{
head=head->next;
free(temp);
return head;
}
linklistp prev = head; //记录前一个结点的指针
temp = head->next;
while (temp != NULL && temp->data !=data) {
prev=temp;
temp=temp->next;
}
if(temp ==NULL) //未查到
return NULL;
prev->next =temp->next;
free(temp);
return head;
}
输出函数及主函数：
//输出函数
void output(linklistp head)
{
linklistp temp=head;
while (temp)
{
printf("%d ",temp->data);
temp=temp->next;
}
printf("\n");
}
int main(int argc, const char * argv[]) {
//定义头结点为空
linklistp head=NULL;
int i=0;
for(i=0;i<10;i++)
{
//申请一个节点，大小为LinkNode
//初始化申请的节点
linklistp newnode=(linklistp)malloc(sizeof(Linknode));
newnode->data=random()%100;
newnode->next=NULL;
head=insert_head(head,newnode);
//head=insert_tail(head,newnode);
output(head);
}
int data=0,data2=0;
printf("Input nodes should be insert：");
scanf("%d",&data2);
linklistp newnode=(linklistp)malloc(sizeof(Linknode));
newnode->data=random()%100;
head=insert_local(head,data2,newnode);
output(head);
printf("Input nodes should be removed：");
scanf("%d",&data);
linklistp temp = delnode(head, data);
if(temp==NULL)
{
printf("To remove the node failure /n");
}
else
{
head=temp;
output(head);
}
return 0;
}
如有不足或不当的地方感谢大家能及时指出。
