数据结构-行列 - 数据结构-顺序表 - Hash表标题整数hash-HDOJ1425（转载）

当前位置: 编程技术>移动开发

本页文章导读:

▪数据结构-行列数据结构--队列队列是只允许在表的一端进行插入（队尾），在另一端进行删除（对头）的运算受限的线性表。允许删除的一端称为对头（front），允许插入的一端称为队尾（rear）。队列.........

▪ 数据结构-顺序表数据结构--顺序表线性表由n（n>=0）个数据元素（结点）组成的有限（线段）序列。记为： (a0,a1,......,an-1) 其中，数据元素个数n称为表的长度，n=0时，称此线性表为空表。 .........

▪ Hash表标题整数hash-HDOJ1425（转载） Hash表题目整数hash-HDOJ1425（转载）哈希表（散列表）的基本原理：使用一个下标范围比较大的数组来存储元素，一般通过设计一个函数（哈希函数，即散列函数），使得每个元素的关键字都.........

[1]数据结构-行列

来源: 互联网发布时间: 2014-02-18

数据结构--队列
队列是只允许在表的一端进行插入（队尾），在另一端进行删除（对头）的运算受限的线性表。

允许删除的一端称为对头（front），允许插入的一端称为队尾（rear）。

队列称为先进先出（First in first out）的线性表。

基本运算

InitQueue（Q）

构造一个空队列Qv

QueueEmpty（Q）

判断队空，若队列Q空，则返回true，否则返回false

QueueFull（Q）

判断队满，若队列为满，则返回true，否则返回false，此操作只适应线性表的队列。

EnQueue（Q,x）

入队，若队列Q非满，则将元素x插入Q的队尾。

DeQueue（Q）

出队，若队列Q非空，则删除Q的对头元素，并返回该元素。

QueueFront（Q）

若队列Q非空，则返回队头元素，注意不改变队列Q的状态。

队列必须使用一个变量保存队列的元素个数。

由于队列的对头和队尾的位置是变化的，因此我们设置两个指针front和rear分别指示对头元素和队尾元素在队列中的位置，他们的初值为0。

入队时将新元素插入到rear所指向的位置，然后将rear加1

出队的时候，返回front所指的元素，然后将front加1

在非空的队列中，头指针始终指向对头元素，而尾指针始终指向最后一个元素+1的位置。

循环队列的取模运算

i=(i+1)%QUEUESIZE;

顺序队

#define QUEUESIZE 100

typedef char DataType;

typedef struct

{

int nFront; //头指针

int nRear; //尾指针

int nCount; //计数器

DataType data[QUEUESIZE];

}CirQueue;

初始化

void InitCQ(CirQueue *c)

{

c->nCount=0;

c->nFront=0;

c->nRear=0;

}

判断队空

int QueueEmply(CirQueue *q)

{

return q->nCount==0;

}

判断队满

bool QueueFull(CirQueue *q)

{

return q->nCount==QUEUESIZE;

}

入队

bool EnQueue(CirQueue *p,DataType _data)

{

if(QueueFull(p))

return false;

p->nCount++;

p->data[p->nRear]=_data;

p->nRear=(p->nRear+1)%QUEUESIZE;

return true;

}

出队

bool DeQueue(CirQueue *p,DataType *data)

{

if(QueueEmpty(p))

return false;

*data=p->data[p->nFront];

p->nFront=(p->nFront+1)%QUEUESIZE;

p->nCount--;

return true;

}

取队头元素

DataType QueueFront(CirQueue *p)

{

if(QueueEmpty(p))

return -1;

return p->data[p->nFront];

}

链队

typedef char DataType;

typedef struct Node

{

Datatype data;

struct Node *next;

}QueueNode;

typedef struct queue

{

QueueNode *front;

QueueNode *rear;

}LinkQueue;

初始化

void InitQueue(LinkQueue *Q)

{

Q->front=Q->rear=NULL;

}

判断队空

int QueueEmpty(LinkQueue *Q)

{

return Q->front==NULL;

}

入队

void EnQueue(LinkQueue *Q,DataType x)

{

QueueNode *p=(QueueNode *)malloc (sizeof(QueueNode));

p->data=x;

p->next=NULL;

if(QueueEmpty(Q))

Q->front=Q->rear=p;

else

{

Q->rear->next=p;

Q->rear=p;

}

出队

DataType DeQueue(LinkQueue *Q)

{

DataType x;

QueueNode *p;

if(QueueEmpty(Q))

return -1;

p=Q->front;

x=p->data;

Q->front=p->next;

if(Q->rear==p)

Q->rear=NULL;

free(p);

return x;

}

取队头元素

DataType QueueFront(LinkQueue *Q)

{

if(QueueEmpty(Q))

return -1;

return Q->front->data;

}

[2] 数据结构-顺序表

来源: 互联网发布时间: 2014-02-18

数据结构--顺序表
线性表

由n（n>=0）个数据元素（结点）组成的有限（线段）序列。

记为：

(a0,a1,......,an-1)

其中，数据元素个数n称为表的长度，n=0时，称此线性表为空表。

n=0时：为空表

n不=0时：n为表长

线性表的结构仅涉及诸元素的线性相对位置。

例如：

第i个元素ai处在第i-1个元素ai-1的后面，第i+1个元素ai+1的前面。

逻辑结构

ai-1被称为是ai的直接前趋，但如果ai是第一个元素的话他没有直接前趋。

ai+1被称为是ai的直接后继，但如果ai是最后一个元素的话他没有直接后继。

基本操作

初始化操作，构造一个空的线性表L

InitList（L）

初始化做的工作就是清空线性表。

求表长，求出线性表L中的结点个数。

ListLength（L）

取线性表L中的第i个结点

GetNode（L,i） i表示第i个位置

要求：0<=i<=ListLength(L)-1

如果不存在，则返回NULL

查找结点

LocateNode（L，x）

在L中查找值为x的结点，并返回该结点在L中的位置，若L中共有多个结点的值和x相同，则返回首次找到的结点位，若L中没有结点值为x，则返回-1表示失败。

插入结点

InsertList（L,x,i）

在线性表L的第i个位置上插入一个值为x的新结点，原第i个位置结点以及后面的结点一次向后面移动一个位置。

注：

0<=i<=n-1，n为原来L的长度，加入x后L的长度为n+1

容错保护：

如果i<0,则让i=0，如果i>n，则让他变成i=n.

删除结点

DeleteList（L,i）

删除线性表L的第i个结点，原第i个位置结点被删除，i+1以及后面的结点依次向前移动一位

注：

0<=i<=n-1，n为原来L的长度，删除第i个位置上的结点后长度变为n-1

顺序表

把线性表的结点按逻辑次序依次放在一组地址连续的存储单元里。这种存储方式就是顺序表（Sequentail List）。

#define LISTSIZE 100 //表的长度，根据实际情况而定

typedef int DataType; //数据 typedef的作用是给类型起别名（可以使程序修改变得简单）给int起了个别名 DataType

struct Seqlist //顺序表

{

DataType data[LISTSIZE]; //存放所有数据的空间

int nLength; //当前表的长度

};

总结：

插入和删除一个数据元素时，其时间主要耗费在移动元素上，而移动元素的个数取决于插入和删除元素的位置。

空间不能充分利用，扩展能力较差。

若线性表的操作主要进行查找以及随机存取表中任一元素，少做插入和删除操作时，采用顺序表存储结构为宜。

六个函数

//初始化
void init(struct Seqlist* s)
{
    s->nLength=0;
}
//输出表内容
void printf(Seqlist* s)
{
    for (int i=0;i<s.nLength;i++)
    printf("%d",s.data[i]);
}
//表长度
int  ListLength(Seqlist* s)
{
    return s->nLength;
}
//取线性表L中的第i个结点
DataType* GetNode(Seqlist* s,int i)
{
    if (i>=0&&i<=s->nLength-1)
         return &s->data[i];
    else
        return NULL;
}
// 查找结点
int LocateNode(const Seqlist* s,const DataType x)
{
    for (int i=0;i<s->nLength-1;i++)
        if(x==s->data[i])
            return i;
    return -1;
}
//插入结点
bool InsertList(Seqlist* s,int data,int index)
{
    if (s->nLength>=LISTSIZE)
        return false;
    if(index>s->nLength-1)
        s->data[s->nLength]=data;
    else
    {
        if(index<0)
            index =0;
        for (int i=s->nLength-1;i>=index;i--)
            s->data[i+1]=s->data[i];
        s->data[index]=data;
    }
    s->nLength++;
    return true;
}
//删除结点
bool DeleteList(Seqlist* s,int i)
{
    if (i<0||s->nLength-1)
        return false;
    else
    {
        for (int j=i;j<s->nLength-1;j++)
            s->data[j]=s->data[j+1];

        s->nLength--;
        return true;
    }
}

[3] Hash表标题整数hash-HDOJ1425（转载）

来源: 互联网发布时间: 2014-02-18

Hash表题目整数hash-HDOJ1425（转载）

哈希表（散列表）的基本原理：使用一个下标范围比较大的数组来存储元素，一般通过设计一个函数（哈希函数，即散列函数），使得每个元素的关键字都与一个函数值（即数组下标）相对应，然后用该数组单元来存储对应元素。

下面介绍用两道题目介绍一下hash表的用法：

题目描述：给你n个整数，请按从大到小的顺序输出其中前m大的数。
Input
每组测试数据有两行，第一行有两个数n,m (0<n,m<1000000)，第二行包含n个各不相同，且都处于区间[-500000,500000]的整数。
Output
对每组测试数据按从大到小的顺序输出前m大的数。
这个问题我们可以看到数据量很大而且整数处于[-500000,500000]之间，那么我们就可以用一个大的数组进行hash，然后进行统计。

 1 #include "stdio.h"
 2 #include "memory.h"
 3  int a[1000001];
 4 int main()
 5 {
 6     int n,m;
 7     int tmp;
 8     int i;
 9     int count;
10     int flag = 0;
11     while(scanf("%d%d",&n,&m)!=EOF)
12     {
13         count = 0;
14         memset(a,0,sizeof(a[0])*1000001);
15         for(i= 0;i<n;i++)
16         {
17             scanf("%d",&tmp);
18             a[tmp+500000]=1;
19         }
20         flag = 0;
21         for(i=1000000;i>=0;i--)
22         {
23             if(a[i]!=0)
24             {
25                 if(!flag)
26                 {
27                     printf("%d",i-500000);
28                     flag = 1;
29                 }
30                 else
31                 {
32                     printf(" %d",i-500000);
33                 }
34               count++;
35             }
36         
37             if(count==m)
38                 break;
39         }
40         printf("\n");
41     }
42     return 0;
43 
44 }