精选文章

Android下使用TCPDUMP抓包Wireshark分析数据 如果想分析Android下某个APP的网络数据交互,需要在Android手机上抓包,最常用的抓包工具非tcpdump莫属,用tcpdump生成Wireshark识别的pcap文件,然后将pcap文件下载到电脑上,用电脑上的Wireshark加载pcap文件,通过Wireshark分析tcpdump抓取的数据。...

继续阅读

Mac下部署Android开发环境附加NDK 作为开发者,我们深有体会,不管是进行什么开发,为了部署开发环境,我们往往需要折腾很长时间、查阅很多资料才能完成,而且这次折腾完了,下次到了另一台新电脑上又得重新来过,整个部署过程记得还好,要是不记得又得重新开始,而且遇到Android这种GFW阻隔了开发资源下载链接的环境部署,又尤其浪费时间。所以这也是我写下这篇教程的初衷跟动力源泉,希望大家参考了这篇教程以后可以轻轻松松在Mac系统下将Android环境部署好。...

继续阅读

稍顯嚴肅的台中 坦白說,留在腦海中的台中影像並不多,來台灣之前在Booking上只訂到了台中的一家青旅,第一次住青旅有些不習慣,幹什麼都放不開。 同屋的一個男生是台灣人,不過一年中四分之三的時間在上海跟北京,這麼說來跟我還是比較有共同話題的。得之我準備花15天的時間環島,覺得太倉促了,他們大學時期花一個半月的時間也不見得能將台灣島給逛完。我只能無奈地表示,兩岸允許的簽證時間有限,自己的空閒時間更有限,只能用打卡式的旅行了,我深知正真地旅行應該慢下來,融入當地的環境,感受他們的風土人情,但第一次只能這樣作罷,以後換成民進黨上台,形勢會變成怎樣還不得而知,能否再過來還是個未知數。而我一向信奉的人生格言是秉燭夜遊,活在當下,所以,理解自己吧。...

继续阅读

為之留戀的新竹 來新竹之前本沒有對她有過高的期待,慢慢對她加分要從桃園火車站出發前往新竹開始。 在桃園火車站的候車月台上,有醒目的旅遊資料發放處,這上面的擺放的全是新竹的旅遊宣傳資料,關鍵的是資料做得非常簡潔易懂,而接下來一天的新竹之行就全部是依據這份寶典的指引來完成的。...

继续阅读

從桃園開始台灣之行 初到台灣恰逢華夏銀行系統升級,特意準備的華夏銀聯卡在桃園機場沒能派上用場,只好用建行在機場5000塊,算下來是很不划算的,但是沒辦法,誰叫我出機場就得花錢呢。 從機場打車到桃園的酒店,花了將近六百塊新台幣,到酒店時五點多,天已經漸亮了,洗漱完等到七點吃過早餐就開始補覺囉,一覺醒來已是中午,帶著換下來的衣服外出找自助洗衣店,順便覓食。...

继续阅读

  • Prev
  • Next

线性表的类型定义及顺序表示和实现

文章分类 : C语言, 应用与编程, 数据结构

1、线性结构的特点是:数据元素的非空有限集中,(1)存在惟一的一个被称做“第一个”的数据元素;(2)存在惟一的一个被称做“最后一个”的数据元素;(3)除第一个之外,集合中的每个数据元素均只有一个前驱;(4)除最后一个之外,集合中每个数据元素均只有一个后继。

2、线性表是n个数据元素的有限序列。

3、C语言实现A = A∪B 算法伪代码

void union(List &La, List Lb)
{
    //将所有在线性表Lb中但不在La中的数据元素插入到La中
    La_len = ListLength(La);
    Lb_len = ListLength(Lb); //求线性表的长度
    for (i = 1; i < Lb_len; i++)
    {
        GetElem(Lb, i, e); //取Lb中第i个数据元素赋给e
        if (!LocalElem(La, e, equal))
            ListInsert(La, ++La_len, e); //La中不存在和e相同的数据元素,则插入之

    }
}

时间复杂度:O(ListLength(LA)XListLength(LB))

4、已知线性表LA和LB中的数据元素按值非递减有序排列,要求将LA和LB归并为一个新的线性表LC,且LC中的数据元素仍按非递减有序排列。C语言实现该算法伪代码如下:

void MergeList(List La, List Lb, List &Lc)
{
    //已知线性表La和Lb中的数据元素按值非递减排列
    //归并La和Lb得到新的线性表Lc,Lc的数据元素也按值非递减排列。
    InitList(Lc);
    i = j = 1; k = 0;
    La_len = listLength(La); Lb_len = listLength(Lb);
    while ((i <= La_len) && (j <= Lb_len))
    {
        GetElem(La, i, ai);GetElem(Lb, j, bj);
        if (ai <=bj) {ListInsert(Lc, ++k, ai); ++i;}
        else {ListInsert(Lc, ++k, bj); ++j}
    }
    while (i <= La_len)
    {
        GetElem(La, i++, ai);
        ListInsert(Lc, ++k, ai);
    }
    while (j <= Lb_len)
    {
        GetElem(Lb, j++, bj);
        ListInsert(Lc, ++k, bj);
    }
}
时间复杂度:O(ListLength(LA)+ListLength(LB))

5、假设线性表的每个元素需占用l个存储单元,则线性表的第i个元素ai的存储位置为LOC(ai) = LOC(a1)+(i-1)*l。

6、C语言实现线性表的动态分配顺序存储结构伪代码:

#define LIST_INIT_SIZE 100 //线性表存储空间的初始分配量
#define LISTINCREMMENT 10 //线性表存储空间的分配增量
typedef struct {
    ElemType *elem; //存储空间基址
    int length; //当前长度
    int listsize; //当前分配的存储容量(以sizeof(ElemType)为单位)
}SqList;
Status InitList_Sq(SqList &L)
{
    //构造一个空的线性表L。
    L.elem = (ElemType *)malloc(LIST_INIT_SIZE*sizeof(ElemType));
    if (!L.elem) exit(OVERFLOW); //存储分配失败
    L.length = 0; //空间长度为0
    L.listsize = LIST_INIT_SIZE; //初始存储容量
    return OK;
}

7、C语言实现在顺序表L中第i个位置之前插入新的元素e,伪代码如下:

Status ListInsert_Sq(SqList &L, int i, ElemType e)
{
    //i的合法值为1<=i<=ListLength_Sq(L)+1
    if (i<1 || i>ListLength_Sq(L)+1) return ERROR; //i值不合法
    if (L.length >= L.listsize)
    {
        //当前存储空间已满,增加分配
        newbase = (ElemType *)realloc(L.elem, (L.listsize+LISTINCREMENT)*sizeof(ElemType));
        if (!newbase) exit(OVERFLOW); //存储分配失败
        L.elem = newbase; //新基址
        L.listsize += LISTINCREMENT; //增加存储容量
    }
    q = &(L.elem[i-1]); //q为插入位置
    for (p = &(L.elem[L.length-1]); p >= q; --p) *(p+1) = *p;
    //插入位置及之后的元素右移
    *q = e; //插入e
    ++L.length; //表长增1
    return OK;
}
时间复杂度:O(n)

8、C语言实现在顺序表L中删除第i元素,并用e返回其值,伪代码如下:

Status ListDelete_Sq(SqList &L, int i, ElemType &e)
{
    if ((i < 1) || (i > L.length)) return ERROR;
    p = &(L.elem[i-1]); //p为被删除元素的位置
    e = *p; //被删除元素赋值给e
    q = L.elem+L.length-1; //表尾元素的位置
    for (++p; p <= q; ++p) *(p-1) = *p; //被删除元素之后的元素左移
    --L.length; //表长减1
    return OK;
}
时间复杂度:O(n)

9、C语言实现顺序线性表L中查找第1个值与e满足compre()的元素位置,伪代码如下:

int LocateElem.Sq(SqList L, ElemType e, Status (* compare)(ElemType, ElemType))
{
    //若找到,则返回其在L中的位序,否则返回0
    i= 1; //i的初始值为第一个元素的位序
    p = L.elem; //p的初值为第一个元素的存储位置
    while (i<=L.length && !(* compare)(*p++, e)) ++i;
    if (i <= L.length) return i;
    else return 0;
}
时间复杂度:O(L.length)

10、已知顺序线性表La和Lb中的数据元素按值非递减有序排列,要求将Lb和Lb归并为一个新的顺序线性表Lc,且Lc中的数据元素仍按非递减有序排列。C语言实现该算法伪代码如下:

void MergeList_Sq(SqList La, SqList Lb, SqList &Lc)
{
    pa = La.elem; pb= Lb.elem;
    Lc.listsize = Lc.length = La.length + Lb.length;
    pc = Lc.elem = (ElemType *)malloc(Lc.listsize*sizeof(ElemType));
    if (!Lc.elem) exit(OVERFLOW); //存储分配失败
    pa_last = La.elem + La.length - 1;
    pb_last = Lb.elem + Lb.length - 1;
    while (pa <= pa_last && pb <= pb_last)
    {
        if (*pa <= *pb) *pc++ = *pa++;
        else *pc++ == *pb++;
    }
    while (pa <= pa_last) *pc++ = *pa++; //插入La的剩余元素
    while (pb <= pb_last) *pc++ = *pb++; //插入Lb的剩余元素
}
时间复杂度:O(La.length+Lb.length)

 



除非注明,文章均为CppLive 编程在线原创,转载请注明出处,谢谢。

本文地址:http://www.cpplive.com/html/1179.html

无觅相关文章插件,快速提升流量