数据存储（链表与数组）

数据存放在内存中，在内存中的组织形式只有两种：

 

衡量一个算法是否优越：

• 时间复杂度（耗费时间）
• 空间复杂度（占用内存） 

1、数组的管理 

int a[100]；//就是在内存中申请100个连续的sizeof（int）空间
int *p = malloc(100xsizeof(int))；//在堆空间中申请100个连续的int空间

对空间进行访问：得到第10个成员，则a[9]，O(1)的成员访问时间（这里O(1)指的是时间复杂度，代表固定的时间，与变量无关）。

如果要在这100个空间中插入/删除一个数，需将后面所有的成员后移/前移。所以数组一般不会去添加或删除成员，其最大的优点是可以一次性访问某个成员，借助了数组下标的优越性。

2、数组的应用

要得出1~127这些范围中某个数的二进制编码中，从低位开始，第一次出现1的bit位编号。

例如：3——>0000 0011——>bit0   4——>0000 0100——>bit2

一个比较简单的方法：
如果data&0x01 == 1 ，已经找到这个bit位号了
否则data>>1,循环检测
虽然最多检测8次，但是我们仍然没有办法固定得到这个值的具体时间。

可以构建一个表：a[127] = {0，1，0，2，0，1，0，3......}
随便输入一个1~127之间的数n，可直接得到结果为a[n]。这样就能够在确定的时间内得到期望的结果。缺点是要事先构建表，占用内存空间。

3、链表的添加操作和删除链表结点

#include<stdio.h>
#include<stdlib.h>

typedef struct linklist
{
    int data;//可以是字符，结构体，指针等
    struct linklist *next;//指向自己结构体类型的指针，单链表
}linknode,*linklistp;

//在头部添加
linkslitp insert_head(linklistp head,linklistp newnode)
{
        newnode->next = head;
        head = newnode;
        return head;
}

//在尾部添加
linklistp insert_tail(linklistp head,linklist newnode)
{
    if(head==NULL)
    {
        newnode->next=NULL;
        head = newnode;
    }
    else
    {
        linklistp temp = head;
        while(temp->next!=NULL)
        {
           temp = temp->next;
        }
        temp->next = newnode;
        newnode->next = NULL;
    }
    return head;
}

//在中间某个位置添加
linklistp insert_local(linklist head,linklistp newnode,int data)
{
     linklistp temp = head;
	 if (temp == NULL)
		 return NULL;
	 if (data == temp->data)
	 {
		 newnode->next = head;
		 head = newnode;
		 return head;
	 }	
	 linklistp prev = head;
	 temp = head->next;
	 while (temp != NULL && data != temp->data)
	 {
		 prev = temp;
		 temp = temp->next;
		 if (temp == NULL)
			 return NULL;
	 }
	 prev->next = newnode;
	 newnode->next = temp; 
	 return head;
}

//删除链表中的某个结点
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()
{
    linklistp head = NULL;
    int a[10] = { 0,1,2,3,4,5,6,7,8,9 };
    for(int i=0;i<10;i++)
    {
       linklistp newnode = (linklistp)malloc(sizeof(linknode));
       newnode->data = a[i];
       //分别在头部尾部添加
       head = insert_tail(head,newnode);//head = insert_head(head,newnode);
       output(head);
       //getchar();//用于调试看    
    }     
    
    //在链表某个位置插入
	int data;
	linklistp newnode2 = (linklistp)malloc(sizeof(linknode));
	newnode2->data = 66;
	printf("pls input need insert data:");
	scanf_s("%d", &data);
	linklistp result1 = insert_local(head, newnode2, data);
	if (result1 == NULL)
		printf("del failure or not has this node \n");
	else
		output(result1);   

    //删除链表中某个结点
	printf("pls input need del data:");
	scanf_s("%d", &data);
	linklistp result2 = delnode(head, data);
	if (result2 == NULL)
		printf("del failure or not has this node \n");
	else
		output(result2);

}