C语言数据结构复习

所谓数据结构，其实就是数据在内存中存储的方式。不同结构提供不同的数据存储方式。

为什么会有这么多种数据结构？原因就是不同数据结构适用不同的算法，让我们的程序跑得更快，资源利用得更加充分。

那么总结一下几种数据结构：线性表（顺序存储结构和链式存储结构，所以也叫顺序表和链表）；

typedef struct
{
        int data[1024];
        int last;          
}sequenlist;

void Initlist(sequenlist* &L)
{
　　　　 L=(sequenlist*)malloc(sizeof(sequenlist));
　　　　 L->last=0;
}

从顺序表的定义中就可以看出，其操作的特点：逻辑相邻则物理位置也相邻；操作时需要移动大量元素，效率低；最大表长难以估计。因此就可以选用链表。

typedef struct node
{
     int data;
     struct node* next;    
}linklist;
linklist*Createlist()
{
　　　linklist*head,*p;
　　　head=(linklist*)malloc(sizeof(linklist));
　　　head->next=NULL;
　　　return head;
}
linklist*get(linklist*head,int i)
{
　　 linklist*p=head;
　　 int j=0;
　　 while(p->next!=NULL&&j<i)
　　　{
　　　　p=p->next;
　　　　j++;
　　　}
　　 if(i==j)return p;
　　　　else return NULL;
}

他是动态存储空间，C语言中的两个标准生成和释放函数：p=(linklist*)malloc(sizeof(linklist));free(p);

此外还有循环链表，双向列表。针对两种存储结构，如果对线性表的操作以查找为主，采用顺序存储结构；若以插入和删除为主，则采用链式存储结构。

栈和队列（两种存储方式，因为也是线性的），可称为运算受限的线性表。

typedef struct
{
     int data[1024];
     int TOP;
}seqstack;

这里面TOP就是指针（和真正的指针不一样，这里就是个序号）；跟数组下表有点类似。

typedef struct node
{
      int data;
      struct node*next;
}stacknode;
typedef struct
{
         stacknode*TOP;   
}linkstack;

链栈不会出现上溢情况，但是会下溢；栈的应用：在数制转换以及编译程序中的表达式求值、函数递归调用等。下面给出一个使用栈的，例子，作为自己的记录：

/****************栈的例子****************/
typedef struct node{
    int data;
    struct node*next;
}stacknode;

typedef struct
{
    stacknode* TOP;
}linkstack;

void initstack(linkstack*&S)
{
    S=(linkstack*)malloc(sizeof(linkstack));
    S->TOP=NULL;
}

void push(linkstack*S,int e)
{
    stacknode*p=(stacknode*)malloc(sizeof(stacknode));
    p->data=e;
    p->next=S->TOP;
    S->TOP=p;
}

int empty(linkstack*S)
{
    if(S->TOP<=0)    return 1;
    else    return 0;
}

int pop(linkstack*S,int &e)
{
    stacknode *p=S->TOP;
    if(empty(S))
    {
        printf("xiayi");
        return 0;
    }
    else
    {
        e=p->data;
        S->TOP=p->next;
        free(p);
        return 1;
    }
}
void conversion(int y,int base)
{
    linkstack *S;
    int bit;
    initstack(S);
    while(y!=0)
    {
        push(S,y%base);
        y=y/base;
    }
    while(!empty(S))
    {
        pop(S,bit);
        if(bit>9) printf("%c",bit+55);
        else printf("%c",bit+48);
    }
    printf("
");
}

int main()
{
    int y=1348;
        conversion(y,8);    
}

View Code

队列，是先进先出，跟栈的先进后出，形成对比。也称FIFO。

树，树形结构是非线性数据结构。二叉树最常用。

根据存储结构，可以有顺序存储和链式存储，顺序存储必须把二叉树转化为完全二叉树，缺点也很明显，具有很多虚节点。

typedef char datatype;
typedef struct node
{
     datatype data;
     struct node *lchild,*rchild;
}bitree;
bitree *root;

hash表及其算法。

这里加入了一个特殊的数据结构，是因为Linux内核很多地方时hash表组织的，所以这里将hash算法复习一下。

http://blog.csdn.net/v_july_v/article/details/6256463

其实hash表就是为了解决链表不易查找而出现的。它结合了链表和数组的优点，从容完成大型数据的快速查找和操作。