Alvar Nuñez Cabeza De Vaca had quite an adventure.
The Death Valley '49ershad some hard times, too.
If you’re not against POW stories, how about Five Years To Freedom by Colonel James ‘Nick’ Rowe?
A good read by one of the handful of Americans to successfully escape from captivity during the Vietnam War. He went on to found the U.S. Army’s Survival, Evasion, Resistance and Escape (SERE) program.
Homer: [reading] Then I heard the sound that all Arctic explorers dread… the pitiless bark of the sea lion! [gasp] He’ll be killed!
Marge: Homer, he obviously got out alive if he wrote the article.
Homer: Don’t be so… [flips ahead] Oh, you’re right.
Waris Dirie is a somali woman who fled home, made it to the UK, was discovered by a photographer and is now a UN Goodwill Ambassador. She’s doing a lot of work fighting ablation and has written two books. My mother’s book club was recently reading Desert Children; I could only take a peek but it seemed well-written.
Hostage in Peking, by Anthony Grey. Grey was a British journalist in China at the time of the Cultural Revolution. He was arrested, held as a political hostage by the Red Guards, and subjected to beatings and other unpleasantries before eventually being released and returned to the UK. Hostage in Peking is his first-hand account of his experience.
83 Hours 'Til Dawn, by Barbara Jane Mackle with Gene Miller. Mackle was kidnapped and held in an underground “capsule” until the ransom was paid. This book is the story of Mackle’s experience in the buried box. It may be out of print now (Amazon shows me nothing), but you may be able to find it through other used book sources or at a public library.
You do yourself a disservice by cutting out mountain climbing situations: the movie Touching the Void (I haven’t read the book) is one of the most incredible survival accounts I’ve ever seen. What’s most jaw-dropping is that the events are being narrated by the two climbers involved, and so you know that they made it out alive; you just don’t see how it’s possible.
Short version: A pair of seasoned climbers tackle the west face of Siula Grande, gaining the summit. On the way down, one of the climbers, Joe Simpson, falls and breaks his tibia. His partner, Simon Yates, must see him down the mountain. They tie themselves together with a few hundred feet of rope, and Yates slowly lowers Simpson down the treacherous mountainside.
Disaster strikes a second time when Simpson, inching down the mountain, suddenly plunges over a cliff, and he is left dangling in midair, unable to do anything to change his situation. Yates can feel Simpson’s full weight on the line, but has no way to communicate with him or pull him up. After an hour, Yates makes the agonizing decision to cut the line, and Simpson falls into an ice crevasse. Yates, knowing that Simpson must have died, makes his way to the base alone.
Simpson, however, did not die. And over the next three days, with a broken leg and no food or water, he somehow pulled himself out of the crevasse and hopped five miles to his base camp over rocky terrain.
That right there is some seriously awesome determination to live. I should note that Simpson does not bear any ill will toward Yates for cutting the line, which in light of what he went through is also pretty phenomenal.
**Alexander Dolgun’s Story: An American in the Gulag ** is the story of an American citizen who was picked up by the KGB in Moscow for questioning and ended up spending 20 years in Soviet prisons. If you want a story about surviving a difficult situation, it doesn’t get any better than this!
David by his mother, Marie Rothenberg. The story of a seven year old boy who survived being doused with gasoline and set on fire by his father.
I have to second this. This book really changed my life. It really makes you think about the things you take for granted and what perspective you should have on your life. Further than that it makes you think about what the meaning of your life should be. Quite possibly the best book I’ve ever read.
There is also a first person account of this event, Miracle in the Andes, by Nando Parado, one of the rugby players on the plane.
Art Spiegelman’s Maus.
My wife read her book, Desert Flower, about Dirie’s own childhood, and said it was very good.
My own recommendations are Shohei Ooka’s Fires on the Plain and Taken Captive, semi-fictionalized accounts of his experiences in WWII. In the second, the ‘difficult situation’ that he and his fellow soldiers face is mainly dealing with the fact that they were living better as POWs than the Japanese civilians back home.
I was going to suggest this one, but since you stole my thunder, I’ll just nitpick…it was the Sierras. 
Yes, I was coming to say that judging from the book reviews, Desert Flower is more what the OP is looking for. Desert Children centers more on her work fighting genital mutilation in Europe. Still a very interesting book that makes you think but not a survival story.
Surprisingly, I have to say the same things about this book. Absolutely amazing.
Completely unbelievable, but eerie at the same time. Not my normal reading, but I blew through it in an very short time.
Bravo Two Zero, Andy McNabb.
[Bravo Two Zero (B20) was the name given to an eight-man British Special Air Service patrol that was tasked with severing the main communication line between Baghdad and north-west Iraq and finding and destroying Iraqi Scud missile launchers during the Gulf War. Bravo Two Zero was the patrol’s callsign. The controversial patrol, mostly a fiasco from the start, has been the subject of several books and two TV movies.
The poorly-equipped patrol then attempted a gruelling march of nearly 300 km (over 186 miles) to exfiltrate northwest to the Syrian border. The team lost contact with each other through miscommunication and became separated while suffering freezing weather, including snowstorms. Three members of the team died, another four were captured and only one, Chris Ryan, reached Syria after eight days.
The captured soldiers were moved numerous times, enduring torture and interrogation at each successive location. They were last held at Abu Ghraib Prison before their release.](Bravo Two Zero - Wikipedia)
Survive the Savage Sea by Dougal Robertson. Family adrift after sailboat sank under them.
Sailboat (not the one in question, honest!)
Patricia Hearst’s “Every Secret Thing.” A lot of people have the basic facts of her ordeal totally wrong.