数据结构复习笔记(1)

  1. 云栖社区>
  2. 博客>
  3. 正文

数据结构复习笔记(1)

嗯哼9925 2017-12-27 15:14:00 浏览688
展开阅读全文
1. 数据的物理存储方式有4种:1)顺序存储。2)链式存储。3)索引存储。4)散列存储

2. 判断算法时间复杂度的根据是当n趋向无穷大时函数的极限,确定时间复杂度的步骤是:1)计算算法的语句频度。2)由语句频度给出时间复杂度。

例:

    void f(int n)
{
        int i = 91,j=100;
        while(j>0)
        {
            if(i>100)
            {
                x-=10;
                y--;
            }
            else
                i++;
        }
}

因为while循环与n无关,所以T(n)=O(1)。

3,一个顺序表L=(a1,a2…an),设计一个算法,要求用最少的时间把所有值为负数的元素,移动到全部值为正数的前面。
分析:题目中的“最少的时间”就意味着时间复杂度为O(n).

 #include <stdio.h>

struct SqList
{
        int data[20];//顺序表存储空间
        int length;//当前长度
};

void Move(struct SqList &L)
{
        int i = 0,j = L.length-1;
        int tmp;
        while(i<j)
        {
            while(L.data[i]<=0)i++;
            while(L.data[j]>=0)j--;
            if(i<j)
            {
                tmp = L.data[i];
                L.data[i] = L.data[j];
                L.data[j] = tmp;
            }
        }
}
void travel(struct SqList &L)
{
        int i = 0;
        while(i<L.length)
        {
            printf("%d\t",L.data[i++]);
        }
}
int main()
{
        struct SqList L;
        int i = 0;
        L.length = 10;
        while(i<10)
        {
            L.data[i++] = -i;
            L.data[i++] = i;
        }
        i = 0;
        travel(L);
        Move(L);
        travel(L);
        return 0;
}

4.顺序表A=(a1,a2…an,b1,b2…bm),将A换成(b1,b2…bm,a1,a2..an),要求不能够用额外的辅助空间。

分析:由于没有说m=n,所以不能够用“对应元素互换”不行,因此先将整个表逆置,再分别逆置两个子表。

void Sq_Reverse(SqList &L,int begin,int end)
{
        int i,j;
        ElemType tmp;
        for(i=begin,j=end;i<end;i++,j--)
        {
            tmp = L.data[i];
            L.data[i] = L.data[j];
            L.data[j] = tmp;
        }
}

void process(SqList &L,int m,int n)
{
        Sq_Reverse(0,m+n-1);
        Sq_Reverse(0,n-1);
        Sq_Reverse(n,m+n-1);
    }


注:比较单链表的逆置:


void Link_Reverse(LinkList &head)
{
        LNode *p = head->next,*q;
        head->next = NULL;
        while(p!=NULL)
        {
            q = p->next;
            p->next = head->next;
            head->next = p;
            p = q;
        }
}

5.为了合并两个各自含有n个元素的有序表LA和LB,在最坏情况下,至少要2n-1次比较。

6.Head是带头结点的单链表的头指针,编写递归算法,逆序输出表中各个元素的值。

    void Output(LNode *head)
{
        if(head!=NULL)
        {
            Output(head->next);
            printf("%d",head->data);
        }
}


7.简单选择排序带头结点的双向链表

void SelectSort(DLinkList &L)
{
        DLink *p,*q,*r;
        p = L->next;
        while(p!=NULL)
        {
            q = p->next;
            r = p;
            while(q!=NULL)
            {
                if(q->data<r->data) r = q;
                q = q->next;
            }
            if(r!=p)
            {
                tmp = p->data;
                p->data = r->data;
                r->data = tmp;
            }
            p = p->next;
        }


8,确定N个数中的第K大者。
#include <stdio.h>

int a[]={9,2,4,5,6,8,5,3};

int k=4,n=8;

void sort(int a[],int n)
{
    int i,j,tmp;
    for(i=0;i<n;i++)
        for(j=i+1;j<n;j++)
        {
            if(a[i]<a[j])
            {
                tmp = a[i];
                a[i] = a[j];
                a[j] = tmp;
            }
        }
}
void travle(int a[],int n)
{
    int i;
    for(i=0;i<n;i++)
    {
        printf("%d\t",a[i]);
    }
    printf("\n");
}

void process(int a[],int num,int n)
{
    int i=0,j;
    while(i<n&&a[i]>=num)i++;
    for(j=k-2;j>=i;j--)
    {
        a[j+1] = a[j];
    }
    a[i] = num;
}

int main()
{
    int i;
    travle(a,n);
    sort(a,k);
    for(i=k;i<n;i++)
    {
        process(a,a[i],n);
    }
    travle(a,n);
    printf("%d\n",a[3]);
    return 0;
}



本文转自Phinecos(洞庭散人)博客园博客,原文链接:http://www.cnblogs.com/phinecos/archive/2006/09/08/499052.html,如需转载请自行联系原作者

网友评论

登录后评论
0/500
评论
嗯哼9925
+ 关注