線性表練習(xí)題

初始設(shè)置

#define OK 1
#define ERROR 0

/* ElemType類型根據(jù)實(shí)際情況而定挑童，這里假設(shè)為int */
typedef int ElemType;
/* Status是函數(shù)的類型,其值是函數(shù)結(jié)果狀態(tài)代碼累铅，如OK等 */
typedef int Status;

// 鏈表結(jié)構(gòu)設(shè)計(jì)
typedef struct Node {
    ElemType data;
    struct Node *next;
} Node, *LinkList;

// 初始化
Status ListInit(LinkList *L, ElemType array[], int count)
{
    LinkList tail = (LinkList)malloc(sizeof(Node));
    if (!tail) return ERROR;
    *L = tail;
    for (int i = 0; i < count; i++) {
        tail->next = (LinkList)malloc(sizeof(Node));
        if (!tail->next) return ERROR;
        tail->next->data = array[i];
        tail = tail->next;
    }
    tail->next = NULL;
    return OK;
}

// 遍歷 
void PrintList(LinkList L)
{
    LinkList tail = L->next;
    while (tail) {
        printf("%3d", tail->data);
        tail = tail->next;
    }
    printf("\n");
}

1. 題目1

將2個(gè)遞增的有序鏈表合并為?個(gè)鏈表的有序鏈表。

要求：

結(jié)果鏈表仍然使?兩個(gè)鏈表的存儲(chǔ)空間站叼，不另外占?其他的存儲(chǔ)空間娃兽。
表中不不允許有重復(fù)的數(shù)據(jù)。

解答

因?yàn)椴荒苷加眯碌目臻g尽楔，即空間復(fù)雜度是 $O(1)$ 投储。

我們只需要使用某一個(gè)鏈表頭作為輸出結(jié)果的表頭，這里我使用L1阔馋。

想象條根鏈表玛荞，通過(guò)一根針串起來(lái)。L1和L2的遍歷指針呕寝，誰(shuí)小就移動(dòng)誰(shuí)勋眯，相等時(shí)同時(shí)移動(dòng)。比如下圖示意3<4下梢，p1移動(dòng)到5客蹋。

需要注意的是，L2中重復(fù)的節(jié)點(diǎn)需要釋放孽江，否則會(huì)內(nèi)存泄露讶坯。

示意圖

時(shí)間復(fù)雜度： $O(n)$

空間復(fù)雜度： $O(1)$

Status MergeTwoLists(LinkList *L1, LinkList *L2, LinkList *L3)
{
    // 另一個(gè)表為空表
    if (L1 == NULL || !(*L1)->next) {
        *L3 = *L2;
        return OK;
    } else if (L2 == NULL || !(*L2)->next) {
        *L3 = *L1;
        return OK;
    }
    // 初始化
    LinkList p1, p2, pre, tmp;
    p1 = (*L1)->next;
    p2 = (*L2)->next;
    *L3 = pre = *L1; // 確定表頭為L(zhǎng)1
    while (p1 && p2) {
        if (p1->data < p2->data) { // <
            pre->next = p1;
            pre = p1;
            p1 = p1->next;
        } else if (p1->data > p2->data) { // >
            pre->next = p2;
            pre = p2;
            p2 = p2->next;
        } else { // ==
            pre->next = p1;
            pre = p1;
            p1 = p1->next;
            tmp = p2; // 準(zhǔn)備釋放相同的數(shù)
            p2 = p2->next;
            free(tmp);
        }
    }
    pre->next = p1 ? p1 : p2;
    return OK;
}

int main(int argc, const char * argv[]) {
    LinkList L1, L2, L3;
    ElemType a[6] = {1, 3, 5, 6, 7, 9};
    ElemType b[6] = {2, 4, 5, 6, 8, 10};
    ListInit(&L1, a, 6);
    ListInit(&L2, b, 6);
    MergeTwoLists(&L1, &L2, &L3);
    PrintList(L3);
    return 0;
}
// 輸出
  1  2  3  4  5  6  7  8  9 10

2. 題目2

已知兩個(gè)鏈表A和B分別表示兩個(gè)集合，其元素遞增排列竟坛。設(shè)計(jì)?個(gè)算法闽巩，用于求出A與B的交集，并存儲(chǔ)在A鏈表中担汤。
例如 : La = {2,4,6,8}; Lb = {4,6,8,10}; 輸出La = {4,6,8}涎跨。

解答

思路和題目1類似，要求結(jié)果存放于L1崭歧，那么我們就選L1作為輸出結(jié)果的表頭隅很。

同樣是雙指針遍歷，誰(shuí)小就移動(dòng)誰(shuí)率碾，相等時(shí)同時(shí)移動(dòng)叔营。但這一次需要釋放L1中不用的節(jié)點(diǎn)。

先釋放比L2中小的部分所宰，取交集之后绒尊，如果p1還沒(méi)有到頭，說(shuō)明還有更大的元素仔粥，需要釋放這部分婴谱。最后尾節(jié)點(diǎn)置空蟹但。

時(shí)間復(fù)雜度： $O(n)$

空間復(fù)雜度： $O(1)$

Status intersection(LinkList *L1, LinkList *L2, LinkList *L3)
{
    if (L1 == NULL || L2 == NULL) return ERROR;
    // 初始化
    LinkList p1, p2, pre, tmp;
    p1 = (*L1)->next;
    p2 = (*L2)->next;
    *L3 = pre = *L1; // 確定表頭為L(zhǎng)1
    while (p1 && p2) {
        if (p1->data < p2->data) { // <
            tmp = p1; // 釋放小于部分
            p1 = p1->next;
            free(tmp);
        } else if (p1->data > p2->data) { // >
            p2 = p2->next;
        } else { // ==
            pre->next = p1;
            pre = p1;
            p1 = p1->next;
            p2 = p2->next;
        }
    }
    while (p1) { // 釋放大于部分
        tmp = p1;
        p1 = p1->next;
        free(tmp);
    }
    pre->next = NULL;
    return OK;
}

int main(int argc, const char * argv[]) {
    LinkList L1, L2, L3;
    ElemType a[4] = {2, 4, 6, 8};
    ElemType b[4] = {4, 6, 8, 10};
    ListInit(&L1, a, 4);
    ListInit(&L2, b, 4);
    intersection(&L1, &L2, &L3);
    PrintList(L3);
    return 0;
}
// 輸出
  4  6  8

3. 題目3

設(shè)計(jì)?個(gè)算法，將鏈表中所有節(jié)點(diǎn)的鏈接方向"原地旋轉(zhuǎn)"谭羔。

僅利用原表的存儲(chǔ)空間华糖，即要求算法空間復(fù)雜度為O(1)。
例如：L={0,2,4,6,8,10}瘟裸，逆轉(zhuǎn)后：L = {10,8,6,4,2,0}客叉。

解答

單鏈表的逆序。需要前一個(gè)節(jié)點(diǎn)和后一個(gè)節(jié)點(diǎn)的指針话告，方便指針逆向兼搏，和繼續(xù)遍歷。

時(shí)間復(fù)雜度： $O(n)$

空間復(fù)雜度： $O(1)$

Status reverse(LinkList *L1)
{
    if (*L1 == NULL) return ERROR;
    LinkList pre = NULL, cur = *L1, next = (*L1)->next;
    while (next) {
        cur = next;
        next = next->next;
        cur->next = pre;
        pre = cur;
    }
    (*L1)->next = cur;
    return OK;
}

int main(int argc, const char * argv[]) {
    LinkList L1;
    ElemType a[6] = {0, 2, 4, 6, 8, 10};
    ListInit(&L1, a, 6);
    reverse(&L1);
    PrintList(L1);
    return 0;
}
//輸出
 10  8  6  4  2  0

4. 題目4

設(shè)計(jì)?個(gè)算法超棺，刪除遞增有序鏈表中值大于等于mink且?于等于maxk(mink向族、maxk是給定的兩個(gè)參數(shù)，值可以和表中的元素相同棠绘，也可以不同)的所有元素件相。

解答

單向鏈表節(jié)點(diǎn)的刪除。不知道是否還有更好的方法氧苍。

時(shí)間復(fù)雜度： $O(n)$

空間復(fù)雜度： $O(1)$

Status delete(LinkList *L1, ElemType mink, ElemType maxk)
{
    if (*L1 == NULL) return ERROR;
    LinkList pre = *L1, cur = (*L1)->next, tmp;
    while (cur) {
        if (mink <= cur->data && cur->data <= maxk) {
            tmp = cur;
            pre->next = cur->next;
            cur = cur->next;
            free(tmp);
        } else {
            pre = cur;
            cur = cur->next;
        }
    }
    return OK;
}

int main(int argc, const char * argv[]) {
    LinkList L1;
    ElemType a[6] = {0, 2, 4, 6, 8, 10};
    ListInit(&L1, a, 6);
    delete(&L1, 1, 7);
    PrintList(L1);
    return 0;
}
// 輸出
  0  8 10

5. 題目5

設(shè)將n(n>1)個(gè)整數(shù)存放到?維數(shù)組R中夜矗，試設(shè)計(jì)?個(gè)在時(shí)間和空間兩?面都盡可能高效的算法。將R中保存的序列循環(huán)左移p個(gè)位置(0<p<n)個(gè)位置让虐，即將R中的數(shù)據(jù)由(x0,x1,......,xn-1)變換為 (xp,xp+1,...,xn-1,x0,x1,...,xp-1)紊撕。

例如：pre[10] = {0,1,2,3,4,5,6,7,8,9}, n = 10,p = 3; pre[10] = {3,4,5,6,7,8,9,0,1,2}

解答

這里直接思路是：

每次取頭數(shù)字
后面的元素前移1格
把最后一個(gè)改為頭數(shù)字

這個(gè)時(shí)間復(fù)雜度是 $O(np)$
。

我們注意到先逆序{9,8,7,6,5,4,3,2,1,0}赡突，然后把3-9和0-2再分別逆序就可以了对扶。

時(shí)間復(fù)雜度： $O(n)$

空間復(fù)雜度： $O(1)$

void Reverse(ElemType a[], int left, int right)
{
    if (left > right) return;
    int mid = (left + right) / 2;
    ElemType tmp;
    for (int i = 0; i <= mid - left; i++){
        tmp = a[left + i];
        a[left + i] = a[right - i];
        a[right - i] = tmp;
    }
}

void MoveLeft(ElemType a[], int n, int p)
{
    Reverse(a, 0, n-1);
    Reverse(a, 0, n-1-p);
    Reverse(a, n-p, n-1);
}

int main(int argc, const char * argv[]) {
    int n = 10, p = 3;
    ElemType *array = (ElemType *)malloc(sizeof(ElemType) * n);
    for (int i = 0; i < n; i++) {
        array[i] = i;
    }
    MoveLeft(array, n, p);
    for (int i = 0; i < n; i++) {
        printf("%d ", array[i]);
    }
    printf("\n");
    free(array);
    return 0;
}
// 輸出
3 4 5 6 7 8 9 0 1 2

6. 題目6

已知?個(gè)整數(shù)序列列A = (a0,a1,a2,...an-1)，其中0<=ai<=n, 0<=i<=n惭缰。若存在ap1= ap2 = ...=apm = x浪南，且m>n/2, 0<=pk<n,1<=k<=m，則稱x為A的主元素漱受。

例如络凿，A=(0,5,5,3,5,7,5,5)，則5是主元素; 若B=(0,5,5,3,5,1,5,7)昂羡，則B中沒(méi)有主元素絮记。

假設(shè)A中的n個(gè)元素保存在?個(gè)一維數(shù)組中，請(qǐng)?jiān)O(shè)計(jì)?個(gè)盡可能?效的算法虐先，找出數(shù)組元素中的主元素怨愤，若存在主元素則輸出該元素，否則輸出-1蛹批。

解答

注意到主元素滿足數(shù)量大于總數(shù)的一半憔四。那么主元素?cái)?shù)量減去其他元素?cái)?shù)量肯定是大于0的膀息。

也可以理解為，主元素和其他元素依次抵消了赵，剩下的肯定是主元素。

利用這個(gè)思路甸赃，從第一個(gè)元素開(kāi)始作為主元素柿汛，下一個(gè)元素若和它相等，計(jì)數(shù)加一埠对，否則減一络断。當(dāng)計(jì)數(shù)為0的時(shí)候，將主元素替換為下一個(gè)元素项玛。

時(shí)間復(fù)雜度： $O(n)$

空間復(fù)雜度： $O(1)$

#define NOT_FOUND -1
int FindMainElement(ElemType *a, int count)
{
    if (a == NULL || count == 0) return NOT_FOUND;
    // 統(tǒng)計(jì)出現(xiàn)較多的數(shù)
    int statistics = 1;
    ElemType mainElem = a[0];
    for (int i = 1; i < count; i++) {
        if (a[i] == mainElem) {
            ++statistics;
        } else {
            --statistics;
        }
        if (statistics == 0) {
            statistics = 1;
            mainElem = a[i];
        }
    }
    // 出現(xiàn)較多貌笨，但不一定滿足主元素?cái)?shù)量>n/2的條件
    if (statistics > 0) {
        statistics = 0;
        for (int i = 1; i < count; i++)
            if (a[i] == mainElem) ++statistics;
        if (statistics > count / 2)
            return mainElem;
    }
    return NOT_FOUND;
}

int main(int argc, const char * argv[]) {   
    ElemType a[8] = {0,5,5,3,5,7,5,5};
    int mainElem = FindMainElement(a, 8);
    if (mainElem > 0) {
        printf("The main element is %d.\n", mainElem);
    } else {
        printf("The main element is not found.\n");
    }
    return 0;
}
// 輸出
The main element is 5.

7. 題目7

?單鏈表保存m個(gè)整數(shù)，結(jié)點(diǎn)的結(jié)構(gòu)為(data, link)襟沮，且|data|<=n(n為正整數(shù))∽锻铮現(xiàn)在要去設(shè)計(jì)一個(gè)時(shí)間復(fù)雜度盡可能高效的算法。對(duì)于鏈表中的data絕對(duì)值相等的結(jié)點(diǎn)开伏，僅保留第?次出現(xiàn)的結(jié)點(diǎn)膀跌，刪除其余絕對(duì)值相等的結(jié)點(diǎn)。

例如固灵，鏈表A = {21,-15,15,-7,15}捅伤，刪除后的鏈表A={21,-15,-7}。

解答

這個(gè)只要求時(shí)間復(fù)雜度盡可能高效巫玻，潛臺(tái)詞就是說(shuō)丛忆，我們可以拿空間換時(shí)間。

我們用一個(gè)char表來(lái)記錄某個(gè)元素是否出現(xiàn)過(guò)仍秤，如果出現(xiàn)過(guò)為1熄诡，否則為0。再次出現(xiàn)時(shí)徒扶，刪除對(duì)應(yīng)節(jié)點(diǎn)粮彤。

又由于條件 $|data|<=1$ ，那么表的大小為 $n+1$ 姜骡。

時(shí)間復(fù)雜度： $O(n)$

空間復(fù)雜度： $O(n)$

Status RemoveAbsRepeat(LinkList *L, int n)
{
    char *flag = (char *)calloc(n + 1, sizeof(char));
    if (flag == NULL) return ERROR;
    LinkList pre, cur, tmp;
    pre = *L;
    cur = pre->next;
    while (cur) {
        int value = cur->data > 0 ? cur->data : cur->data * -1;
        if (flag[value - 1]) {
            tmp = cur;
            cur = cur->next;
            pre->next = cur;
            free(tmp);
        } else {
            flag[value - 1] = 1;
            pre = cur;
            cur = cur->next;
        }
    }
    free(flag);
    return OK;
}

int main(int argc, const char * argv[]) {
    LinkList L1;
    ElemType a[6] = {0, 15, 3, -3, -15, 2};
    ListInit(&L1, a, 6);
    RemoveAbsRepeat(&L1, 16);
    PrintList(L1);
    return 0;
}
// 輸出
  0 15  3  2

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者

人面猴
序言：七十年代末导坟，一起剝皮案震驚了整個(gè)濱河市，隨后出現(xiàn)的幾起案子圈澈，更是在濱河造成了極大的恐慌惫周，老刑警劉巖，帶你破解...
沈念sama閱讀 221,548評(píng)論 6贊 515
死咒
序言：濱河連續(xù)發(fā)生了三起死亡事件康栈，死亡現(xiàn)場(chǎng)離奇詭異递递，居然都是意外死亡喷橙，警方通過(guò)查閱死者的電腦和手機(jī)，發(fā)現(xiàn)死者居然都...
沈念sama閱讀 94,497評(píng)論 3贊 399
救了他兩次的神仙讓他今天三更去死
文/潘曉璐我一進(jìn)店門登舞，熙熙樓的掌柜王于貴愁眉苦臉地迎上來(lái)贰逾，“玉大人，你說(shuō)我怎么就攤上這事菠秒「斫＃” “怎么了？”我有些...
開(kāi)封第一講書(shū)人閱讀 167,990評(píng)論 0贊 360
道士緝兇錄：失蹤的賣姜人
文/不壞的土叔我叫張陵践叠，是天一觀的道長(zhǎng)言缤。經(jīng)常有香客問(wèn)我，道長(zhǎng)禁灼，這世上最難降的妖魔是什么管挟？我笑而不...
開(kāi)封第一講書(shū)人閱讀 59,618評(píng)論 1贊 296
?港島之戀（遺憾婚禮）
正文為了忘掉前任，我火速辦了婚禮弄捕，結(jié)果婚禮上僻孝，老公的妹妹穿的比我還像新娘。我一直安慰自己察藐，他們只是感情好皮璧，可當(dāng)我...
茶點(diǎn)故事閱讀 68,618評(píng)論 6贊 397
惡毒庶女頂嫁案：這布局不是一般人想出來(lái)的
文/花漫我一把揭開(kāi)白布。她就那樣靜靜地躺著分飞，像睡著了一般悴务。火紅的嫁衣襯著肌膚如雪。梳的紋絲不亂的頭發(fā)上譬猫，一...
開(kāi)封第一講書(shū)人閱讀 52,246評(píng)論 1贊 308
城市分裂傳說(shuō)
那天讯檐，我揣著相機(jī)與錄音，去河邊找鬼染服。笑死别洪，一個(gè)胖子當(dāng)著我的面吹牛，可吹牛的內(nèi)容都是我干的柳刮。我是一名探鬼主播挖垛，決...
沈念sama閱讀 40,819評(píng)論 3贊 421
雙鴛鴦連環(huán)套：你想象不到人心有多黑
文/蒼蘭香墨我猛地睜開(kāi)眼，長(zhǎng)吁一口氣：“原來(lái)是場(chǎng)噩夢(mèng)啊……” “哼秉颗！你這毒婦竟也來(lái)了痢毒？” 一聲冷哼從身側(cè)響起，我...
開(kāi)封第一講書(shū)人閱讀 39,725評(píng)論 0贊 276
萬(wàn)榮殺人案實(shí)錄
序言：老撾萬(wàn)榮一對(duì)情侶失蹤蚕甥，失蹤者是張志新（化名）和其女友劉穎哪替，沒(méi)想到半個(gè)月后，有當(dāng)?shù)厝嗽跇?shù)林里發(fā)現(xiàn)了一具尸體菇怀，經(jīng)...
沈念sama閱讀 46,268評(píng)論 1贊 320
?護(hù)林員之死
正文獨(dú)居荒郊野嶺守林人離奇死亡凭舶，尸身上長(zhǎng)有42處帶血的膿包…… 初始之章·張勛以下內(nèi)容為張勛視角年9月15日...
茶點(diǎn)故事閱讀 38,356評(píng)論 3贊 340
?白月光啟示錄
正文我和宋清朗相戀三年晌块，在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了。大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片帅霜。...
茶點(diǎn)故事閱讀 40,488評(píng)論 1贊 352
活死人
序言：一個(gè)原本活蹦亂跳的男人離奇死亡匆背，死狀恐怖，靈堂內(nèi)的尸體忽然破棺而出身冀，到底是詐尸還是另有隱情靠汁，我是刑警寧澤，帶...
沈念sama閱讀 36,181評(píng)論 5贊 350
?日本核電站爆炸內(nèi)幕
正文年R本政府宣布闽铐，位于F島的核電站，受9級(jí)特大地震影響奶浦，放射性物質(zhì)發(fā)生泄漏兄墅。R本人自食惡果不足惜，卻給世界環(huán)境...
茶點(diǎn)故事閱讀 41,862評(píng)論 3贊 333
男人毒藥：我在死后第九天來(lái)索命
文/蒙蒙一澳叉、第九天我趴在偏房一處隱蔽的房頂上張望隙咸。院中可真熱鬧，春花似錦成洗、人聲如沸五督。這莊子的主人今日做“春日...
開(kāi)封第一講書(shū)人閱讀 32,331評(píng)論 0贊 24
一樁弒父案瓶殃，背后竟有這般陰謀
文/蒼蘭香墨我抬頭看了看天上的太陽(yáng)充包。三九已至，卻和暖如春遥椿，著一層夾襖步出監(jiān)牢的瞬間基矮，已是汗流浹背。一陣腳步聲響...
開(kāi)封第一講書(shū)人閱讀 33,445評(píng)論 1贊 272
情欲美人皮
我被黑心中介騙來(lái)泰國(guó)打工冠场，沒(méi)想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留家浇，地道東北人。一個(gè)月前我還...
沈念sama閱讀 48,897評(píng)論 3贊 376
代替公主和親
正文我出身青樓碴裙，卻偏偏與公主長(zhǎng)得像钢悲，于是被迫代替她去往敵國(guó)和親。傳聞我的和親對(duì)象是個(gè)殘疾皇子舔株，可洞房花燭夜當(dāng)晚...
茶點(diǎn)故事閱讀 45,500評(píng)論 2贊 359